$1$ を根とする根付き木が与えられる。第 $i$ 番目の頂点の親は $p_i$ であり、その色は $col_i$ である。ここで $col_i \in \{0, 1\}$ であることが保証される。
Alice と Bob はこの木の上でゲームを行う。両者は交互に操作を行い、Alice が先手である。各操作では、$x=1$ であるか、あるいは $p_x$ がすでに削除されているような頂点 $x$ を一つ選び、その頂点を削除する。
最後に削除された頂点の色が $0$ であれば Alice の勝ち、そうでなければ Bob の勝ちとなる。両者とも勝利のために最善を尽くすものとする。
$T$ 個のテストケースが与えられる。各テストケースについて、勝者を判定せよ。
入力
第一行に正整数 $T$ が与えられ、データセットの数を示す。各データセットの形式は以下の通りである。
- 第一行に正整数 $n$ が与えられる。
- 第二行に $n-1$ 個の正整数 $p_2, p_3, \dots, p_n$ が与えられる。
- 第三行に $n$ 個の非負整数 $col_1, col_2, \dots, col_n$ が与えられる。
出力
各データセットについて、勝者が Alice であるか Bob であるかを一行に出力せよ。
入出力例
入力 1
3 2 1 1 0 5 1 2 2 1 0 0 0 1 0 8 1 2 2 2 1 6 1 1 0 0 0 1 0 1 0
出力 1
Alice Bob Alice
制約
本問題はサブタスク制である。
すべてのデータにおいて、$1 \le T \le 10000$、$1 \le \sum n \le 5 \times 10^5$、$1 \le p_i < i$、$0 \le col_i \le 1$ が保証される。
サブタスク 1 ($20$ 点): $T=1$、$n \le 20$ が保証される。
サブタスク 2 ($30$ 点): すべての $i$ について、$i=1 \lor p_i=1 \lor p_{p_i}=1$ が成り立つことが保証される。
サブタスク 3 ($20$ 点): すべての $i$ について、$i$ が葉であるか、あるいは $i$ を根とする部分木のサイズが偶数であることが保証される。
サブタスク 4 ($30$ 点): 特殊な制限はない。