このゲームはルーピーゲームと呼ばれるゲームで、高速に勝敗判定できることが知られています。

まず、各盤面に対して \(\mathbb{N}_{0} \cup\lbrace\infty \rbrace\) の値を定義します。

\(m_n(G)\) を \(G\to G'\) 全てに対する \(\mathcal{G}_n(G')\) の mex として定義します。

盤面 \(G\) と \(n\geq 0\) に対し、\(\mathcal{G}_n(G)\) を以下のように定義します：

• \(n=0\) のとき：\(G\) が終了局面なら \(\mathcal{G}_0(G)=0\) 、それ以外なら \(\mathcal{G}_0(G)=\infty\)
• \(n > 0\) のとき：
  • \(\mathcal{G}_{n-1}(G') > m_{n-1}(G)\) を満たす \(G\to G'\) 全てに対し、ある \(G'\to G''\) が存在し \(\mathcal{G}_{n-1}(G'')=m_{n-1}(G)\) を満たすとき：\(\mathcal{G}_n(G)=m_{n-1}(G)\)
  • それ以外のとき：\(\mathcal{G}_n(G)=\infty\)

このように定義した際、十分大きい \(n\) に対して \(\mathcal{G}_{n+1}(G)=\mathcal{G}_n(G)\) が成り立ちます。（今回の問題であれば \(n=N-1\) 以上で成り立ちます）

十分大きい \(n\) に対して \(\mathcal{G}_n(G)=m\) が成り立つ時、\(\mathcal{G}(G)=m\) と書きます。それ以外の場合 \(\mathcal{A}=\lbrace \mathcal{G}(G') \in \mathbb{N}_{0} \ |\ G\to G'\rbrace\) として \(\mathcal{G}(G)=\infty(\mathcal{A})\) と書きいます。このようにして定義した \(\mathcal{G}(G)\) を \(G\) のルーピーグランディ数と呼びます。

このように定義した \(\mathcal{G}(G)\) に対し、盤面 \(G_1,G_2\) の直和のルーピーグランディ数 \(\mathcal{G}(G_1+G_2)\) が盤面 \(G_1,G_2\) のルーピーグランディ数 \(\mathcal{G}(G_1),\mathcal{G}(G_2)\) から計算できることがわかっています。

具体的には、\(\infty (\mathcal{A})\oplus b=\infty(\mathcal{A}\oplus b)\) 、\(\infty(\mathcal{A}) \oplus \infty (\mathcal{B})=\infty(\empty)\) と定義すると \(\mathcal{G}(G_1+G_2)=\mathcal{G}(G_1)\oplus\mathcal{G}(G_2)\) という等式が成り立ちます。

さらに、盤面 \(G\) のルーピーグランディ数 \(\mathcal{G}(G)\) から以下のように勝敗判定を行うことができます：

• \(\mathcal{G}(G)=0\) のとき：後手必勝。
• \(\mathcal{G}(G)=m > 0\) のとき：先手必勝。
• \(\mathcal{G}(G)=\infty(\mathcal{A})\) であって \(0\in \mathcal{A}\) のとき：先手必勝。
• \(\mathcal{G}(G)=\infty(\mathcal{A})\) であって \(0\not\in \mathcal{A}\) のとき：引き分け。

以上を元に適切に実装することでこの問題に正答することができます。計算量は \(O(N(N+M))\) です。

コマの置かれた頂点でルーピーグランディ数が整数でない頂点が \(2\) つ以上存在する場合引き分けとなることを用いて実装してください。

---

参考：安福智明・坂井公・末續鴻輝『組合せゲーム理論の世界 ―数学で解き明かす必勝法―』共立出版, 2024.