Code

#include <bits/stdc++.h>
using namespace std;

class UnionFind {
  public:
    int n;
    vector<int> parent, sz;

  public:
    UnionFind(int n) {
        this->n = n;
        parent.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    int find_set(int u) {
        if (u == parent[u]) {
            return u;
        }
        int root_u = find_set(parent[u]);
        parent[u] = root_u;
        return root_u;
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);

        if (a != b) {
            parent[a] = b;
            sz[b] += sz[a];
        }
    }
};

vector<long long> solve(int n, vector<pair<int, int>> &edges) {
    int m = edges.size();

    UnionFind dsu(n);

    long long reachable_pairs = 0;
    long long total_pairs = 1LL * n * (n - 1) / 2;

    vector<long long> ans;
    for (int i = m - 1; i >= 0; i--) {
        int x = edges[i].first;
        int y = edges[i].second;
        x--;
        y--;

        ans.push_back(total_pairs - reachable_pairs);

        // Remember that the size should be of leader, not the element.
        if (dsu.find_set(x) != dsu.find_set(y)) {
            reachable_pairs +=
                (1LL * dsu.sz[dsu.find_set(x)] * dsu.sz[dsu.find_set(y)]);
        }

        dsu.union_sets(x, y);
    }

    reverse(ans.begin(), ans.end());
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        edges[i] = make_pair(x, y);
    }

    vector<long long> res = solve(n, edges);
    for (int i = 0; i < (int)res.size(); i++) {
        cout << res[i] << "\n";
    }
}