各頂点に非負整数、または \(\infty\) を割り当てることを考えます。直感的には、非負整数は Grundy 数を、\(\infty\) は必勝であることを表します。

各頂点への値の割り当ては以下の手順で再帰的に行います：

• その頂点から出る色が R の辺が存在しないとき：B の辺を用いて到達できる頂点に割り当てられた値のうち、\(\infty\) を除いた値の \(\text{mex}\) を割り当てる。
• その頂点から出る色が R の辺が存在し、それらが全て同じ非負整数 \(a\) が割り当てられた頂点に向かっているとき：その頂点から出る色が B の辺であって値 \(a\) が割り当てられた頂点が存在するなら \(\infty\) を、存在しないなら \(a\) を割り当てる。
• それ以外のとき：\(\infty\) を割り当てる。

このとき、後手必勝盤面であることは全てのコマの置かれた頂点に書かれた値が有限で、その総 \(\mathrm{XOR}\) が \(0\) であることと同値になります。

証明は帰納法で行うことができます。

\(u_i<v_i\) という制約より、頂点 \(N\) から降順に頂点に割り当てられる値を求めることができます。計算量は \(O(N+M)\) です。