公式解説では動的に色を管理・反転させるアプローチが紹介されていますが、この解説では「クエリを先読みし、あらかじめグラフの色を固定する」方法を紹介します。

1. 事前準備（森の構築と色の固定）

まず初めに、以下の操作を行って森（閉路のないグラフ）を構築します。

• 与えられたクエリの順に処理を行い、頂点 \(u, v\) が非連結である場合は \(u, v\) の間に辺を追加します。すでに連結である場合はなにもしません。

次に、構築された森の各連結成分について、隣り合う頂点が異なる色になるよう、条件を満たすように白・黒の色を任意に決定します。

この事前計算によって一旦各頂点の色を固定します。実際のグラフ全体の彩色は、ここで決めた色でそのまま塗るのではなく、連結成分ごとに「白の個数」と「黒の個数」を比較し、「黒の個数」のほうが多い場合は反転させて塗ることで最終的な答えを得ることとします。

2. クエリのシミュレーション

再度、辺が全く無い状態から各クエリを初めからシミュレーションします。Union-Findの各連結成分のleaderで、「白の頂点数、黒の頂点数」を管理します。

初期状態:

辺が1つも存在しないため、各頂点がそれぞれ独立した連結成分となります。各頂点 \(i\) （自身がleader）の初期値は、以下のように設定します。

• 頂点 \(i\) の事前計算した色が白の場合：白の頂点数 \(= 1\)、黒の頂点数 \(= 0\)
• 頂点 \(i\) の事前計算した色が黒の場合：白の頂点数 \(= 0\)、黒の頂点数 \(= 1\)

また、このとき各連結成分の \(\min(\text{白}, \text{黒})\) はいずれも \(0\) となるため、\(ans = 0\) とします。

クエリごとの操作:

頂点 \(u, v\) を結ぶクエリが与えられたとき、以下のケースに分けて処理を行います。

• ケース 1 : \(u, v\) が同じ連結成分のとき

  • \(u, v\) の（事前計算した）色が異なるなら、なにもしません。
  • \(u, v\) の（事前計算した）色が同じなら、このクエリを含めて以降のクエリに対する答えはすべて \(-1\) とします。

• ケース 2 : \(u, v\) が違う連結成分のとき

  • クエリ処理前のそれぞれの連結成分が \(ans\) に寄与していた分を減算し、結合後の連結成分の寄与分を加算して \(ans\) を更新します。

  \[ ans \leftarrow ans - \min(\text{白}_{u}, \text{黒}_{u}) - \min(\text{白}_{v}, \text{黒}_{v}) + \min(\text{白}_{u} + \text{白}_{v}, \text{黒}_{u} + \text{黒}_{v}) \\ \text{（※ } \text{白}_{u} \text{ は「} u \text{ を含む連結成分の白の頂点数」）} \]

  • \(ansの\)更新後、Union-Find上で \(u, v\) を連結し、新しいleaderに白黒両方の頂点数の合計を格納します。

時間計算量は \(O(N+Q\alpha(N))\) です。

実装例(C++):

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

int main() {
    int N, Q; cin >> N >> Q;
    vector<pair<int, int>> uv(Q);
    for (int i = 0; i < Q; ++i) {
        int u, v; cin >> u >> v;
        uv[i] = { u - 1, v - 1 };
    }

    //事前準備
    vector<vector<int>> graph(N);
    dsu uf1(N);
    for (int i = 0; i < Q; ++i) {
        auto [u, v] = uv[i];
        if (uf1.same(u, v)) continue;
        uf1.merge(u, v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> color(N, -1); //0:白, 1:黒
    for (int i = 0; i < N; ++i) {
        if (color[i] != -1) continue;
        color[i] = 0;
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (auto& nv : graph[v]) {
                if (color[nv] != -1) continue;
                color[nv] = 1 - color[v];
                q.push(nv);
            }
        }
    }

    //クエリ処理
    dsu uf2(N);
    vector<pair<int, int>> count(N, { 0,0 }); //{白の数, 黒の数}
    for (int i = 0; i < N; ++i) {
        count[i] = (color[i] == 0) ? make_pair(1, 0) : make_pair(0, 1);
    }
    int ans = 0;
    for (int i = 0; i < Q; ++i) {
        auto [u, v] = uv[i];
        if (ans != -1) {
            if (uf2.same(u, v)) {
                if (color[u] == color[v]) ans = -1;
            }
            else {
                auto [uW, uB] = count[uf2.leader(u)];
                auto [vW, vB] = count[uf2.leader(v)];
                ans = ans - min(uW, uB) - min(vW, vB) + min(uW + vW, uB + vB);
                const int nl = uf2.merge(u, v);
                count[nl] = { uW + vW, uB + vB };
            }
        }
        cout << ans << "\n";
    }
}