#P9632. Game on Tree

Game on Tree

题目描述

有一棵 NN 个节点的树,节点标号为 1,2,⋯,N1,2,⋯,N,边用 (xi,yi)(x_i,y_i) 表示。 Alice 和 Bob 在这棵树上玩一个游戏,Alice 先手,两人轮流操作:

选择一条树上存在的边,把它断开使树变成两个连通块。然后把不包含 11 号点的联通块删除。

当一个玩家不能操作时输,你需要算出:假如两人都按最优策略操作,谁将获胜。

输入格式

NN

x1x_1 y1y_1

x2x_2 y2y_2

⋯\cdots

xn−1x_{n-1} yn−1y_{n-1}

输出格式

若 Alice 获胜,输出 Alice。

否则输出 Bob。

样例

5
1 2
2 3
2 4
4 5
Alice
5
1 2
2 3
1 4
4 5
Bob
6
1 2
2 4
5 1
6 3
3 2
Alice
7
1 2
3 7
4 6
2 3
2 4
1 5
Bob

数据范围

1≤N≤2000001 \le N \le 200000。

1≤xi,yi≤N1\le x_i,y_i \le N。

保证给出的是一棵树。