N - Adjacent Game 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

N 頂点の木が与えられます。木の頂点には 1, 2, \dots, N の番号がついており、i 番目の辺 (1 ≤ i ≤ N-1) は頂点 u_i と頂点 v_i を結んでいます。

Alice と Bob は、頂点に自分の印をつけることを繰り返すゲームを行います。はじめ、どの頂点にも印はついていません。

まず、Alice が好きな頂点を選んで自分の印をつけます。次に、Bob から始めて交互に次の操作を行います。操作を行えなかった方の負けで、そうでない方の勝ちです。

  • 次の条件を満たす頂点 v をひとつ選ぶ。
    • 頂点 v には印がついていない。
    • 頂点 v と辺で繋がれているある頂点 u が存在して、相手がつけた印がついている。
  • 選んだ頂点 v に自分の印をつける。

両者が自身の勝ちを目指して最適に行動するとき、どちらが勝つかを求めてください。

制約

  • 入力はすべて整数
  • 1\le N\le 2\times 10^5
  • 1\le u_i,v_i\le N
  • 与えられるグラフは木である

入力

入力は以下の形式で標準入力から与えられる。

N
u_1 v_1
\vdots
u_{N-1} v_{N-1}

出力

Alice が勝つなら Alice を、Bob が勝つなら Bob を出力してください。

入力例 1

5
1 2
2 3
3 4
2 5

出力例 1

Alice

例えば、次のようなシナリオが考えられます。

  1. はじめに Alice が頂点 1 に自分の印をつける。
  2. Bob が頂点 2 に自分の印をつける（頂点 1 には相手の印がついており、頂点 2 と辺で繋がっている）。
  3. Alice が頂点 3 に自分の印をつける（頂点 2 には相手の印がついており、頂点 3 と辺で繋がっている）。
  4. Bob が頂点 4 に自分の印をつける（頂点 3 には相手の印がついており、頂点 4 と辺で繋がっている）。
  5. Alice が頂点 5 に自分の印をつける（頂点 2 には相手の印がついており、頂点 5 と辺で繋がっている）。
  6. Bob は操作を行うことができない。Alice の勝ちである。

この木では Alice に必勝法が存在するので、Alice を出力してください。

入力例 2

4
1 2
3 4
3 2

出力例 2

Bob

入力例 3

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

出力例 3

Alice

Score: 100 points

Problem Statement

You are given a tree with N vertices. The vertices of the tree are numbered 1, 2, \dots, N, and the i-th edge (1 \leq i \leq N-1) connects vertex u_i and vertex v_i.

Alice and Bob play a game where they alternately mark vertices with their own markers. Initially, no vertices are marked.

First, Alice chooses any vertex and marks it with her marker. Then, starting with Bob, the two players alternate performing the following operation. The player who cannot make a move loses, and the other player wins.

  • Choose a vertex v that satisfies the following conditions:
    • Vertex v is not marked.
    • There exists a vertex u connected to v by an edge such that u is marked with the opponent's marker.
  • Mark the chosen vertex v with their own marker.

Determine the winner when both players adopt the optimal strategy for their own victory.

Constraints

  • All input values are integers.
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • The given graph is a tree.

Input

The input is given in the following format:

N
u_1 v_1
\vdots
u_{N-1} v_{N-1}

Output

If Alice wins, output Alice. If Bob wins, output Bob.

Sample Input 1

5
1 2
2 3
3 4
2 5

Sample Output 1

Alice

For example, consider the following scenario:

  1. Alice starts by marking vertex 1 with her marker.
  2. Bob marks vertex 2 (vertex 1 is marked by the opponent and is connected to vertex 2 by an edge).
  3. Alice marks vertex 3 (vertex 2 is marked by the opponent and is connected to vertex 3 by an edge).
  4. Bob marks vertex 4 (vertex 3 is marked by the opponent and is connected to vertex 4 by an edge).
  5. Alice marks vertex 5 (vertex 2 is marked by the opponent and is connected to vertex 5 by an edge).
  6. Bob cannot make a move. Alice wins.

In this tree, Alice has a winning strategy, so you should output Alice.

Sample Input 2

4
1 2
3 4
3 2

Sample Output 2

Bob

Sample Input 3

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

Sample Output 3

Alice