Rooted Tree Game

Time Limit : 1 sec, Memory Limit : 262144 KB

Problem E: Rooted Tree Game

Problem

初期状態として複数の根付き木が与えられる。これに対しAliceとBobはゲームを行う。ゲームは2人交互に行い、先手がAliceで後手がBobである。ターンが回ってきたプレイヤーは以下の行動を取る。

  1. 根(親を持たない頂点)を1つ選択する。この頂点をSとする。
  2. Sを根とする根付き木に含まれる頂点を選択する(ここではSも選択可能)。この頂点をTとする。
  3. SからTへの経路上にある頂点を、STも含めすべて削除する。また、削除された頂点が端点であるような辺もすべて削除する。

ターンが回ってきた時点で頂点がすべて削除されていた場合、そのプレイヤーの負けとなる。

AliceとBobが常に最適な行動を取る時、与えられた初期状態に対し、勝利するプレイヤーを判定せよ。

以下の図は、プレイヤーの行動の例を示す。
プレイヤーの行動の例

Input

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

N M
p1
p2
:
pM

1行目に、初期状態の頂点数Nと辺の数Mが空白区切りで与えられる。この時、各頂点を表す番号は1~Nである。次のM行では、辺の情報が与えられる。このうちi行目では1つの整数piが与えられる。これは、頂点piから頂点iへの辺があることを表す。言い換えると、頂点iの親が頂点piであることを表す。

Constraints

入力は以下の制約を満たす。

  • 1 ≤ N ≤ 1000
  • 0 ≤ M < N
  • i < pi ≤ N ( 1 ≤ iM )

Output

勝利するプレイヤーの名前(AliceまたはBob)を1行に出力せよ。

Sample Input1

6 3
4
4
5

Sample Output1

Alice

Sample Input2

6 4
2
5
4
5

Sample Output2

Bob