配点 : 100 点
致环球杯参赛者
当包含在 Universal Cup 中时,此问题将被删除。因此,当使用 AtCoder 结果进行 Universal Cup 时,我们建议先解决其他问题。 给出了
問題文
在顶部 编号为 1 减去 N 它是一个具有 N 给出一棵顶点树。i 第一条边是顶点 u_i 和边 v_i 是平局。爱丽丝和鲍勃在这棵树上玩游戏。 起初,爱丽丝处于顶部。 a ,Bob 是顶点 我在 b 。顶点 a 为红色且顶点 b 为蓝色,其他顶点未着色。
Alice 主导,Alice 和 Bob 轮流执行以下操作。这个操作需要每个玩家 重复直到每 10^{100} 次。
- 与当前所在顶点相邻的顶点 1 选择一个并移动到该顶点。然后,如果您是 Alice,则将移动的顶点的颜色重新绘制为红色;如果您是 Bob,则将其绘制为蓝色(如果已经着色,则覆盖)。
当所有操作完成后,如果画成蓝色的顶点数大于画成红色的顶点数,则Bob获胜;否则(涂成红色的顶点数大于或等于涂成蓝色的顶点数),Alice 获胜。
当双方都为自己的胜利采取最佳行动时确定谁获胜。
制約
- 2 \le N \le 2 \times 10^5
- 1 \le a, b \le N
- a \neq b
- 1 \le u_i, v_i \le N
- 给定的图是一棵树。
- 所有输入均为整数。
入力
输入是按以下格式从标准输入给出的。
N a b
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
出力
如果Alice有获胜方法 Alice ,如果鲍勃有获胜方法 Bob 。
入力例 1
5 1 5 4 3 4 5 3 2 2 1
出力例 1
Bob
入力例 2
6 2 6 6 5 2 1 3 5 4 3 1 3
出力例 2
Bob