AT_pakencamp_2024_day3_1_o Prohibited Area

$ 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 がゲームに勝利できるような数列をひとつ出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ が複数考えられる場合、どれを出力しても正解となる。

### 部分点 - $ U_i = i, V_i = {i+1} $ ( $ 1 \leq i \leq N-1 $ ) を満たすテストケースに正答した場合は、 $ 5 $ 点が与えられる。 ### Sample Explanation 1 このサンプルでは、例えば次のようにゲームが進行します。 - 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 が勝利することが証明できます。 ### Constraints - $ 1 \leq N \leq 2000 $ - $ 1 \leq U_{i}, V_{i} \leq N $ $ (1 \leq i \leq N-1) $ - 与えられるグラフは木である - 入力は全て整数 ---