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

struct DSU {
    vector<int> parent, sz;
    stack<pair<int,int>> history;  // store (u, size[u]) before merge
    int components;

    DSU(int n) {
        parent.resize(n);
        sz.assign(n, 1);
        iota(parent.begin(), parent.end(), 0);
        components = n;
    }

    int find(int x) {
        while (x != parent[x]) x = parent[x];
        return x;
    }

    bool unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;

        if (sz[a] < sz[b]) swap(a, b); // union by size
        history.push({b, sz[a]});      // save state for rollback
        parent[b] = a;
        sz[a] += sz[b];
        components--;
        return true;
    }

    void rollback() {
        if (history.empty()) return;
        auto [b, prevSizeA] = history.top();
        history.pop();
        int a = parent[b];
        parent[b] = b;
        sz[a] = prevSizeA;
        components++;
    }
};

int main() {
    int n = 5;
    DSU dsu(n);

    dsu.unite(0, 1);
    dsu.unite(2, 3);
    cout << "Components: " << dsu.components << "\n"; // 3

    dsu.unite(1, 2);
    cout << "Components: " << dsu.components << "\n"; // 2

    dsu.rollback(); // undo last union
    cout << "Components after rollback: " << dsu.components << "\n"; // 3

    return 0;
}