struct dsu{
    stack<tuple<int, int, int>> st;
    int n;
    vector<int> id;
    vector<vector<int>> comp;
    dsu(int nn){
        n = nn;
        for(int i = 0; i < n;  i++) id.pb(i), comp.pb({i});
    }
    int unite(int a, int b){
        a = id[a], b = id[b];
        if(a == b) return 0;
        if(comp[a].size() > comp[b].size()) swap(a, b);
        st.push({a, b, (int)comp[a].size()});
        while(!comp[a].empty()){
            int x = comp[a].back(); comp[a].pop_back();
            id[x] = b;
            comp[b].pb(x);
        }
        return 1;
    }
    void rollback(){
        auto [a, b, sz] = st.top(); st.pop();
        while(sz--){
            int x = comp[b].back(); comp[b].pop_back();
            id[x] = a;
            comp[a].pb(x);
        }
    }
};