初期状態として複数の根付き木が与えられる。これに対しAliceとBobはゲームを行う。ゲームは2人交互に行い、先手がAliceで後手がBobである。ターンが回ってきたプレイヤーは以下の行動を取る。
ターンが回ってきた時点で頂点がすべて削除されていた場合、そのプレイヤーの負けとなる。
AliceとBobが常に最適な行動を取る時、与えられた初期状態に対し、勝利するプレイヤーを判定せよ。
以下の図は、プレイヤーの行動の例を示す。
入力は以下の形式で与えられる。
N M p1 p2 : pM
1行目に、初期状態の頂点数Nと辺の数Mが空白区切りで与えられる。この時、各頂点を表す番号は1~Nである。次のM行では、辺の情報が与えられる。このうちi行目では1つの整数piが与えられる。これは、頂点piから頂点iへの辺があることを表す。言い換えると、頂点iの親が頂点piであることを表す。
入力は以下の制約を満たす。
勝利するプレイヤーの名前(AliceまたはBob)を1行に出力せよ。
6 3 4 4 5
Alice
6 4 2 5 4 5
Bob