分数: 1100 点
问题陈述
有一棵树 N 顶点编号 1, 2, ..., N。 树的边缘表示为 (x_i, y_i).
在这棵树上,Alice 和 Bob 互相玩游戏。 从Alice开始,他们交替执行以下操作:
- 选择一条现有边并将其从树中删除,将其断开为两个独立的连接组件。然后,删除不包含Vertex的组件 1.
当玩家无法执行该操作时,他/她就输掉了游戏。 假设双方都发挥最佳状态,确定游戏的获胜者。
约束
- 2 \leq N \leq 100000
- 1 \leq x_i, y_i \leq N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
x_1 y_1
x_2 y_2
:
x_{N-1} y_{N-1}
输出
打印 Alice 如果爱丽丝赢了;打印 Bob 如果鲍勃获胜。
示例输入 1
5 1 2 2 3 2 4 4 5
示例输出 1
Alice
如果 Alice 首先删除连接顶点的边 1 和 2,树成为仅包含 Vertex 的单顶点树 1。 由于不再有边,鲍勃无法执行该操作,爱丽丝获胜。
示例输入 2
5 1 2 2 3 1 4 4 5
示例输出 2
Bob
示例输入 3
6 1 2 2 4 5 1 6 3 3 2
示例输出 3
Alice
示例输入 4
7 1 2 3 7 4 6 2 3 2 4 1 5
示例输出 4
Bob