E - 根付き森二人用ゲーム
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
N 個の根付き木があります。それぞれの木は、木 1, 木 2, \ldots , 木 N と名付けられています。 木 i の頂点の数は M_i で、それぞれ頂点 1, 頂点 2, \ldots , 頂点 M_i と名付けられています。 また、木 i の根は頂点 1 で、木 i の頂点 j (2 \leq j \leq M_i) の親は頂点 p_{ij} です。
AliceさんとBobさんが、これらの木と一つのチェスの駒を使ってゲームをしようとしています。ルールは以下のようになっています。
- 最初、駒は「スタート地点」に置かれている。
- プレイヤーはAliceさんから交互に以下の行動を行う。
- もし駒が「スタート地点」にあるならば、まだ選ばれていない木を一つ選び、その木の根に駒を動かす。もし、まだ選ばれていない木が無いならば、現在のプレイヤーは敗北する。
- 駒が木の葉にあるならば、「スタート地点」に駒を動かす。
- 駒が木の葉でない頂点にあるならば、その子頂点のいずれかに駒を動かす。
AliceさんとBobさんが勝利のために最適に行動するとき、勝利するのはどちらになるでしょうか。
制約
- 1 \leq N \leq 10^5
- 2 \leq M_i \leq 10^5
- 1 \leq p_{ij} \leq j-1
- \sum_{i=1}^{N} M_i \leq 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N M_1 p_{12} p_{13} ... p_{1{M_1}} M_2 p_{22} p_{23} ... p_{2{M_2}} \vdots M_N p_{N2} p_{N3} ... p_{N{M_N}}
出力
AliceさんとBobさんが最適に行動したとき、Aliceさんが勝つならAlice
、Bobさんが勝つならBob
と出力せよ。
入力例 1
1 4 1 1 2
出力例 1
Bob
二人は以下のように行動します。
- Aliceさんが、コマを木 1 の根である頂点 1 に動かす。
- Bobさんが、コマを頂点 1 の子である頂点 2 に動かす。
- Aliceさんが、コマを頂点 2 の子である頂点 4 に動かす。
- Bobさんが、頂点 4 は葉なので、コマをスタート地点に動かす。
この後、Aliceさんはもうコマを動かせないので、Bobさんが勝利します。
入力例 2
3 5 1 2 3 4 5 1 2 1 4 10 1 1 1 3 4 2 3 5 6
出力例 2
Bob