← 返回题目列表

AtCoder · pakencamp_2024_day3_1_o

O. 禁止区域

中文机器翻译题面 查看原题

配点 : 100 点

問題文

N 頂点 N-1 给出了一棵边树。在顶部 1, 2, \ldots, N 已编号,i 第一条边是顶点 U_i 与边缘 V_i 双向连接。爱丽丝和鲍勃用这棵树玩以下游戏:

  1. 鲍勃的长度 1 以上 10 \times N 以下序列 告诉爱丽丝 B 。
  2. Alice 选择一个顶点并降落在其上。
  3. Alice 移动到相邻顶点。 重复 n = \lvert B\rvert 次。然而, i 就在第二步之前,顶点 不要在 B_i 中。
  4. 爱丽丝在满足条件时移动。 当且仅当 Alice 能做到 n 次时,她才会获胜。否则,鲍勃获胜。

树的形状和 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) 。
  • 爱丽丝是最上面的 前往 1 开始移动。
  • 爱丽丝是顶点 2 (= B_1) 不存在,因此游戏继续。 转至
  • 爱丽丝是最上面的 前往 2 。
  • 爱丽丝是顶点 3 (= B_2) 不存在,因此游戏继续。 转至
  • 爱丽丝是最上面的 前往 3 。
  • 爱丽丝是顶点 4 (= B_3) 不存在,因此游戏继续。 转至
  • 爱丽丝是最上面的 前往 4 。
  • 爱丽丝是顶点 2 (= B_4) 不存在,因此游戏继续。 转至
  • 爱丽丝是最上面的 前往 5 。
  • 爱丽丝是顶点 3 (= B_5) 不存在,因此游戏继续。 转至
  • 爱丽丝是最上面的 前往 4 。
  • 爱丽丝是顶点 4 (= B_6) 。

这是游戏进展的示例,Alice 和 Bob 可能没有做对他们双方都最好的事情。然而,如果 Bob 传达了输出中所示的序列,则可以证明无论 Alice 做什么,Bob 都会获胜。