ゲームの終了時点で、\(G\) は 頂点 \(1\) を含む連結成分はサイズ \(n\) の、頂点 \(N\) を含む連結成分はサイズ \(N-n\) の２つの完全グラフになります。 このとき、辺の本数は \(N(N-1)/2 - n(N-n)\) 本あります。 手番が交互に訪れることから \(N(N-1)/2 - n(N-n) - M\) が奇数ならば先手の、偶数ならば後手の勝ちとなることがわかります。

ここで \(N\) が奇数のとき、\(n,N-n\) のいずれかはかならず偶数であるため、\(N(N-1)/2 - n(N-n) - M\) の偶奇はどのように手を打ったとしても変化しません。よって、\(N\) が奇数のときは、\(N(N-1)/2 - M\) の偶奇を調べればよいです。

\(N\) が偶数のときは、\(n,N-n\) の偶奇によって \(N(N-1)/2 - n(N-n) - M\) の偶奇は変化してしまいます。 ゲーム開始時点の頂点 \(1\) を含む連結成分はサイズを \(x\)、頂点 \(N\) を含む連結成分のサイズを \(y\) とします。 \(x,y\) の偶奇が異なるならば、先手必勝。そうでないならば \(N(N-1)/2 - xy - M\) が奇数ならば先手の、偶数ならば後手の勝ちとなることが示せます。

\(x,y\) の偶奇が異なるならば、先手は自分が勝つように \(x,y\) の偶奇を変化させるような手をはじめに打てばよいです(これはサイズが奇数の連結成分が必ず偶数個あることから必ず可能です)。その後、後手がどのような手を打ったとしてもその変化を打ち消す、あるいは \(x,y\) の偶奇に影響を与えないような手を打ち続けることができることから先手必勝であることが示せます。

\(x,y\)の偶奇が等しい場合もほぼ同様です、ゲーム開始の時点で \(N(N-1)/2 - xy - M\) が奇数ならば、先手は後手がどのような手を打ったとしてもその変化を打ち消す、あるいは \(x,y\) の偶奇に影響を与えないような手を打ち続ければよく先手必勝です。\(N(N-1)/2 - xy - M\) が偶数の場合もほぼ同様に示すことができ、後手必勝となります。

これは \(O(N+M)\) で判定可能で十分高速です。