\(i=M,M-1,\dots,2,1\) の順に、生徒 \(A_i\) と生徒 \(B_i\) を異なるクラスにいるようにできるならそうする、という貪欲法で解くことができます。

まず、 \(N\) 人ずつという条件がない場合を考えます。これは、次のようにして解くことができます。

\(2N\) 頂点の重み付き Union-Find に \(i=M,M-1,\dots,2,1\) の順に以下の操作を行う。

• 頂点 \(A_i\) と頂点 \(B_i\) が連結でないならその間に距離 \(1\) の辺を貼る

操作後のグラフで、各連結成分についてある頂点を決めその頂点からの距離の偶奇でクラスを分ける

\(N\) 人ずつという条件を追加すると、辺を貼ると条件を満たさなくなることがあります。そのため、辺を貼るときに辺を貼った後に条件を満たすか判定し、満たすときのみ辺を貼ることにします。

連結成分に番号づけして各連結成分 \(i=1,2,\dots, K\) についてある頂点からの距離が偶数である頂点の数を \(x_i\) または奇数である頂点の数を \(y_i\) とすると、 \(\mathrm{dp}[i][j]\) を連結成分 \(1,2,\dots,i\) について \(x_i\) か \(y_i\) を足し合わせたものが \(j\) となるものが存在するか否かの bool 値とし、 \(\mathrm{dp}[K][N]\) を見ることで \(\Theta(N^2)\) 時間で条件を満たすかどうか判定できます。

以上を素直に実装すると、 \(\Theta(N^2M)\) 時間で解くことができます。しかし、 \(N^2M\) は最大で \(2.5\times 10^{13}\) になり間に合わないため、高速化します。

まず、ある \(i\) で辺を追加すると \(N\) 人ずつに分けることが不可能になるとき、 \(A_i\) と \(B_i\) の間に距離 \(0\) の辺を貼ってもよいです。

これにより、 dp を行う回数を高々 \(N-1\) 回に抑えることができます。

次に、 dp 部分を高速化できます。 \(\mathrm{dp}[j]\) を、各連結成分 \(i=1,2,\dots,K\) について \(x_i\) か \(y_i\) を足し合わせたものが \(j\) と等しくなるものの総数とします。連結成分 \(s,t\) の \((x_s,y_s)\) と \((x_t,y_t)\) を merge し \((x_s+x_t,y_s+y_t)\) または \((x_s+y_t,y_s+x_t)\) にした後の dp 配列は、 merge 前の dp 配列を利用するとより高速に求められます。 \(\mathrm{dp}[i]\) は \(f(x)=\prod_{i=1}^{K} (x^{x_i}+x^{y_i})\) の \(x^i\) の係数に等しく、 \(f(x)\) を \(x^{x_s}+x^{y_s}\) で割ることは \(\frac{1}{x^{x_s}+x^{y_s}}\) をかけることに言い換えられ、これは \(x_s=y_s\) のときは容易に、そうでないときは \(\frac{1}{1+x}=1-x+x^2-x^3+\dots\) を用いることで計算できます。同様に \(x^{x_t}+x^{y_t}\) で割り、その後に \(x^{x_s+x_t}+x^{y_s+y_t}\) か \(x^{x_s+y_t}+x^{y_s+x_t}\) をかけることで \(\Theta(N)\) 時間で更新することができました。（戻す dp と呼ばれる手法です）

ただし、 \(\mathrm{dp}\) の値をそのまま求めると値が非常に大きくなるため、適切に整数 \(P\) を選び \(\bmod P\) で値を保存する必要があります。例えば、 \(P\) を \([10^{17},10^{18}]\) の区間にある素数から無作為に選ぶとほとんど失敗しません。

\(\Theta(N)\) 時間かかる dp を \(\Theta(N)\) 回行って、Union-Find にクエリを \(\Theta(M)\) 回投げるため、時間計算量は \(\Theta(N^2+M\alpha(N))\) です。

余談ですが、マージに失敗するたびに \((a,b),(c,d) \rightarrow (a+c,b+d)\) とマージすると \(N\) 人ずつに分けられないという \((a,b,c,d)\) の組をメモすることにします。すると、一度失敗した \((a,b,c,d)\) はもし他のところでマージに成功したとしてももう二度と見る必要がありません。一見あまり意味のないように見えますが、この枝刈りをすることで計算量が実は \(\Theta(N^{\frac{7}{3}})\) に落ちます。証明は読者への課題とします。