O - Prohibited Area Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 頂点 N-1 辺の木が与えられます。頂点には 1, 2, \ldots, N の番号がふられており、i 番目の辺は頂点 U_i と頂点 V_i を双方向に結んでいます。Alice と Bob がこの木を用いて次のようなゲームをします：

  1. Bob が長さ 1 以上 10 \times N 以下の数列 B を Alice に伝える。
  2. Alice が頂点を一つ選び、その頂点に降り立つ。
  3. Alice が隣り合う頂点へ移動することを n = \lvert B\rvert 回繰り返す。ただし、 i 回目の移動の直前に頂点 B_i にいてはいけない。
  4. Alice が条件を満たしながら移動を n 回行うことができた場合、またその場合に限り Alice が勝利する。そうでなかった場合、Bob が勝利する。

木の形状及び Bob の選択は両者に共有されます。両者が自身の勝利を目指して最適な選択をした際にどちらが勝つか判定してください。Bob が勝利すると判定した場合はさらに、Bob がゲームに勝利できるような数列をひとつ出力してください。

制約

  • 1 \leq N \leq 2000
  • 1 \leq U_{i}, V_{i} \leq N (1 \leq i \leq N-1)
  • 与えられるグラフは木である
  • 入力は全て整数

部分点

  • U_i = i, V_i = {i+1} (1 \leq i \leq N-1) を満たすテストケースに正答した場合は、5 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

Alice が勝利すると判定した場合、次を出力せよ。

Alice

Bob が勝利すると判定した場合、次を出力せよ。

Bob
n
B_1 B_2 \cdots B_n

ここで、n は Bob が選ぶ数列 B の長さを表す。よって、1 \leq n \leq 10 \times N 、1 \leq B_i \leq N (1 \leq i \leq n) が満たされる必要がある。

また、出力の通りに Bob が数列を選んだ場合、Alice の行動にかかわらず、Bob が勝利できなければならない。なお、n の値を最小化する必要はない。条件を満たす n,B が複数考えられる場合、どれを出力しても正解となる。

入力例 1

5
1 2
2 3
3 4
4 5

出力例 1

Bob
6
2 3 4 2 3 4

このサンプルでは、例えば次のようにゲームが進行します。

  • Bob が Alice に整数列 (2, 3, 4, 2, 3, 4) を伝える。
  • Alice が頂点 1 から移動を始める。
  • Alice は頂点 2 (= B_1) にいないため、ゲームは継続する。
  • Alice が頂点 2 へ移動する。
  • Alice は頂点 3 (= B_2) にいないため、ゲームは継続する。
  • Alice が頂点 3 へ移動する。
  • Alice は頂点 4 (= B_3) にいないため、ゲームは継続する。
  • Alice が頂点 4 へ移動する。
  • Alice は頂点 2 (= B_4) にいないため、ゲームは継続する。
  • Alice が頂点 5 へ移動する。
  • Alice は頂点 3 (= B_5) にいないため、ゲームは継続する。
  • Alice が頂点 4 へ移動する。
  • Alice は頂点 4 (= B_6) にいるため、Bob の勝利としてゲームは終了する。

これはゲームの進行の一例であり、Alice 、Bob が両者にとって最適な行動をしているとは限りません。しかし、出力の通りに Bob が数列を伝えた場合、Alice がどのような行動をしたとしても Bob が勝利することが証明できます。