分数: 100 点
问题陈述
你得到了一棵树 N 顶点。树的顶点已编号 1, 2, \dots, N,以及 i第边缘 (1 \leq i \leq N-1) 连接顶点 u_i 和顶点 v_i.
Alice 和 Bob 玩一个游戏,他们交替用自己的标记标记顶点。最初,没有标记任何顶点。
首先,Alice 选择任意顶点并用她的标记对其进行标记。然后,从鲍勃开始,两名玩家交替执行以下操作。无法采取行动的玩家失败,另一位玩家获胜。
- 选择一个顶点 v 满足以下条件:
- 顶点 v 未标记。
- 存在一个顶点 u 连接到 v 的边使得 u 上标有对手的标记。
- 标记所选顶点 v 带有自己的标记。
当双方都采取最佳策略以取得胜利时,确定获胜者。
约束
- 所有输入值均为整数。
- 1 \leq N \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N
- 给定的图是一棵树。
输入
输入按以下格式给出:
N
u_1 v_1
\vdots
u_{N-1} v_{N-1}
输出
如果Alice获胜,输出 Alice。如果 Bob 获胜,则输出 Bob.
示例输入 1
5 1 2 2 3 3 4 2 5
示例输出 1
Alice
例如,考虑以下场景:
- Alice 首先标记顶点 1 用她的记号笔。
- Bob 标记顶点 2 (顶点 1 被对手标记并连接到顶点 2 的边缘)。
- Alice 标记顶点 3 (顶点 2 被对手标记并连接到顶点 3 的边缘)。
- Bob 标记顶点 4 (顶点 3 被对手标记并连接到顶点 4 的边缘)。
- Alice 标记顶点 5 (顶点 2 被对手标记并连接到顶点 5 的边缘)。
- Bob 无法移动。爱丽丝赢了。
在这棵树中,Alice 有获胜策略,所以你应该输出 Alice.
示例输入 2
4 1 2 3 4 3 2
示例输出 2
Bob
示例输入 3
7 1 2 2 3 3 4 3 5 1 6 6 7
示例输出 3
Alice