D - Game on Tree Editorial /

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