题目描述

Alice 和 Bob 在树上玩游戏。最初的时候，树上的所有节点都是白色的。

Alice 先手，她可以任选一个节点并在该点上放置一个标记，该点变为黑色。在这之后，玩家轮流进行游戏，每一回合中玩家可以将标记从所在点移动到该点的白色祖先节点或儿子节点中，并将移动到的点变为黑色。无法进行移动的玩家即输。

谁会赢得游戏呢？

在有根树上，节点 $v$ 的祖先节点是指从树根到节点 $v$ 的路径上的任意点。

在有根树上，节点 $v$ 的儿子节点是指满足节点 $v$ 在从树根到节点 $w$ 路径上的任意点 $w$。

规定树的树根为点 $1$。

输入格式

第一行包含一个整数 $n \ (1 \leq n \leq 100 \ 000)$，代表树的节点数。

接下来的 $n-1$ 行中，每一行包含两个整数 $u$ 和 $v \ (1 \leq u, v \leq n)$，代表树上的一条边 $(u, v)$。数据保证这些边会构成一棵树。

输出格式

输出一行，如果 Alice 赢得了游戏，则输出 Alice，否则输出 Bob。

4
1 2
2 3
3 4

Bob

7
2 1
2 6
1 3
2 5
7 2
2 4

Alice

提示

第一组样例中，树的形态是 $4$ 个点的一条链，所以 Bob 总是可以把标记移到最后的白点上。

第二组样例中，Alice 的最佳策略是先把标记放在点 $3$ 上，然后 $3$ 会变为黑色。Bob 只能移动标记到点 $1$ 上。Alice 可以选择点 $4, 5, 6$ 或 $7$ 来移动。Bob 只能选择 $2$。Alice 选择 $2$ 的任一白色子节点，Bob 就无法移动了。