まず、先に手番をプレイできなくなったプレイヤーの負けである場合について考えます。

このゲームは Green Hackenbush Tree として有名で、AtCoder にも出題例があります。(AGC017-D)

先に手番をプレイできなくなったプレイヤーの勝ちである場合はどうなるでしょうか？このように着手できなくなったプレイヤーの勝ちとなるゲームを逆型と呼びます。

一般に逆型の勝敗判定を高速に行うのは難しいですが、Nim や Green Hackenbush Tree などのゲームの場合通常型と似た判定法で勝敗判定ができることが知られています。

まず Nim の逆型について考えます。

Nim の逆型で後手必勝となる条件は以下であることが知られています：

• 全ての山の石の個数が \(1\) である場合：石のある山の個数が奇数
• 石が \(2\) つ以上ある山が存在する場合：石の個数の総 \(\mathrm{XOR}\) が \(0\)

これは通常の Nim 同様帰納法で示すことができます。

Nim の逆型と同様に、Green Hackenbush Tree の逆型で後手必勝となる条件は以下のようになります：

• 全ての辺が根から出ている場合：辺の本数が奇数
• 根から出ていない辺が存在する場合：通常型で後手必勝

証明は逆型の Nim と同様の性質を満たしていることから言えます。

以上を適切に実装することでこの問題に正答することができます。