

Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1100 点
問題文
N 個の頂点 1, 2, ..., N からなる木があります. この木の辺は (x_i, y_i) で表されます.
Alice と Bob は,この木を使ってゲームをします. Alice から始め,Alice と Bob が交互に次の操作を行います.
- まだ残っている辺を選び,その辺を木から取り除く.また,この操作により木は 2 つに分断されるが,そのうち頂点 1 を含まないほうの木も取り除く.
先に操作を行えなくなったほうが負けです. 2 人が最適に行動するとき,どちらが勝つかを求めてください.
制約
- 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 が勝つなら Alice
を,Bob が勝つなら Bob
を出力せよ.
入力例 1
5 1 2 2 3 2 4 4 5
出力例 1
Alice
Alice が最初に頂点 1, 2 を結ぶ辺を選んで操作を行うと,頂点 1 のみを含む木になります. このとき,辺は残っていないので,Bob は操作を行うことができず,Alice が勝ちます.
入力例 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
Score : 1100 points
Problem Statement
There is a tree with N vertices numbered 1, 2, ..., N. The edges of the tree are denoted by (x_i, y_i).
On this tree, Alice and Bob play a game against each other. Starting from Alice, they alternately perform the following operation:
- Select an existing edge and remove it from the tree, disconnecting it into two separate connected components. Then, remove the component that does not contain Vertex 1.
A player loses the game when he/she is unable to perform the operation. Determine the winner of the game assuming that both players play optimally.
Constraints
- 2 \leq N \leq 100000
- 1 \leq x_i, y_i \leq N
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N x_1 y_1 x_2 y_2 : x_{N-1} y_{N-1}
Output
Print Alice
if Alice wins; print Bob
if Bob wins.
Sample Input 1
5 1 2 2 3 2 4 4 5
Sample Output 1
Alice
If Alice first removes the edge connecting Vertices 1 and 2, the tree becomes a single vertex tree containing only Vertex 1. Since there is no edge anymore, Bob cannot perform the operation and Alice wins.
Sample Input 2
5 1 2 2 3 1 4 4 5
Sample Output 2
Bob
Sample Input 3
6 1 2 2 4 5 1 6 3 3 2
Sample Output 3
Alice
Sample Input 4
7 1 2 3 7 4 6 2 3 2 4 1 5
Sample Output 4
Bob