Shared code

#include <bits/stdc++.h>
#define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
using namespace std;
 
const int maxn = 1e5 + 10;
struct Query{
    int u,v;
};
struct DSU_save{
    int u,v,su,sv;
};
 
struct DSU_rollback{
    int par[maxn];
    stack<DSU_save> save;
    int comps;
 
    void init(int n){
        assert(save.empty());
        memset(par, -1, sizeof(par[0])*(n+1));
        comps = n;
    }
 
    int root(int x){
        while (par[x] >= 0) x = par[x];
        return x;
    }
 
    bool combinable(int u, int v){
        u = root(u);
        v = root(v);
        if (u == v) return false;
 
        if (par[u] > par[v]) swap(u, v);
        save.push({u, v, par[u], par[v]});
        --comps;
        par[u] += par[v];
        par[v] = u;
        return true;
    }
 
    bool connected(int u, int v){
        return (root(u) == root(v));
    }
 
    void rollback(){
        if (save.empty()) return; //in fact: "vector<DSU_save>save" never empty
        DSU_save cur = save.top();
        save.pop();
        ++comps;
        par[cur.u] = cur.su;
        par[cur.v] = cur.sv;
    }
};
 
struct Segment_Tree{
    int n;
    vector<vector<Query> > T;
    int conn[maxn];
    DSU_rollback dsu;
 
    void init(int _n, int _q){ //be careful: number of n and q
        n = _q;
        T.clear();
        T.resize((n << 2) + 5);
        dsu.init(_n);
        memset(conn, -1, sizeof(conn[0])*(n+1));
    }
 
    void add_node(int nod, int l, int r, int u, int v, const Query& Q){
        if (l > v || r < u) return;
        if (l >= u && r <= v){
            T[nod].push_back(Q);
            return;
        }
        int mid = (l+r) >> 1;
        add_node(nod*2, l, mid, u, v, Q);
        add_node(nod*2+1, mid+1, r, u, v, Q);
    }
 
    void DFS(int nod, int l, int r){
        int rollcount = 0;
        for (Query& Q : T[nod]){
            if (dsu.combinable(Q.u, Q.v)) ++rollcount;
        }
 
        if (l == r){ //Reach the Query point
            conn[l] = dsu.comps;
        }
        else {
            int mid = (l+r) >> 1;
            DFS(nod*2, l, mid);
            DFS(nod*2+1, mid+1, r);
        }
        while (rollcount--) dsu.rollback();
    }
 
    void add_node(int l, int r, const Query& Q){
        add_node(1, 1, n, l, r, Q);
    }
} Tree;
 
int n,m,q;
vector<int> query_pos;
map<pii, int> M;
void build_tree(){
    up(i,1,m){
        int u,v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        M[{u, v}] = 1;
    }
 
    up(i,2,q+1){
        int type,u,v;
        cin >> type >> u >> v;
        if (u > v) swap(u,v);
        pii cur = {u, v};
 
        if (type == 1) M[cur] = i;
        else {
            Tree.add_node(M[cur], i-1, {u, v});
            M.erase(cur);
        }
    }
 
    for (auto x : M){
        int u = x.first.first;
        int v = x.first.second;
        Tree.add_node(x.second, q+1, {u, v});
    }
}
 
void answer(){
    up(i,1,q+1){
        cout << Tree.conn[i] << " ";
    }
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #define Task "CONNCOMP"
    if (fopen(Task".inp", "r")){
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
 
    cin >> n >> m >> q;
    Tree.init(n, q+1);
    build_tree();
    Tree.DFS(1, 1, q+1);
    answer();
}