E - 根付き森二人用ゲーム /

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