AtCoder Grand Contest 017

D - Game on Tree


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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

Submit提出する