まず、クエリを処理し終えたについて答えを求めます。(このときの答えがです。) このから逆順にクエリを処理することを考えると 辺を取り除く操作は、辺を追加する操作になり、Union-Find を用いることができます。 クエリの処理は以下のように行います。
頂点と頂点を、からに逆順で結ぶことを考えるとき
(1)頂点と頂点が既に連結であるとき
←
頂点と頂点を結ぶ。
(2)頂点と頂点が、連結ではないとき
頂点の属する連結成分の大きさを、頂点の属する連結成分の大きさをとしたとき、
←
頂点と頂点を結ぶ。
実際に答えを求めるときは、割る操作はにおける逆元をかける操作になることに注意して下さい。