树的深度会超过log层，但我找不到原因了，用的深度合并。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>


#define db(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout << '\n';}
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a <<  ' ';
	err(++it, args...);
}


struct Pdsu {
    struct nd {
        int f, sz, l, r;
        // sz 表示深度，不是大小
    };

    int n, tot;
    vector<nd> t;
    Pdsu (int n_, int& u, int sz) {
        n = n_, tot = 0;
        t.assign(sz, {});
        build(u, 1, n);
    }
    void build(int& u, int l, int r) {
        u = ++tot;
        if(l == r) {
            t[u].f = l, t[u].sz = 1;
            return;
        }
        int mid = l + r >> 1;
        build(t[u].l, l, mid); build(t[u].r, mid + 1, r);
    }

    void insert(int v, int &u, int p, int x, int f, int l, int r) {
        if(l > r) return;
        u = ++tot;
        t[u] = t[v];
        if(l == r) {
            if(f == 0) t[u].f = x;
            else t[u].sz = x;
            return;
        }
        int mid = l + r >> 1;
        if(p <= mid) insert(t[v].l, t[u].l, p, x, f, l, mid);
        else insert(t[v].r, t[u].r, p, x, f, mid + 1, r);
    }
    nd get(int u, int p, int l, int r) {
        if(l == r) return t[u];
        int mid = l + r >> 1;
        if(p <= mid) return get(t[u].l, p, l, mid);
        else return get(t[u].r, p, mid + 1, r);
    }
    
    nd fa(int u, int x) {
        int cnt = 0;
        while(1) {
            cnt++;
            // assert(cnt < 100); // 这里会出问题，所以合并的sz肯定没处理好
            auto p = get(u, x, 1, n);
            if(p.f == x) return p;
            x = p.f;
        }
    }

    void merge(int v, int& u, int x, int y) {
        nd p = fa(v, x), q = fa(v, y);

        if(p.f == q.f) {
            u = v;
            return;
        }

        if(p.sz > q.sz) swap(p, q); 
            
        int tmp = 0;
        insert(v, tmp, p.f, q.f, 0, 1, n);
        insert(tmp, u, q.f, max(q.sz, p.sz + 1), 1, 1, n);
        return;
    }
    bool same(int u, int x, int y) {
        nd p = fa(u, x), q = fa(u, y);
        if(p.f == q.f) return 1;
        return 0;
    }
    
};

void solve() {
    int n, m;
    cin >> n >> m;
    
    vector<int> rt(m + 1);
    Pdsu dsu(n, rt[0], m * 27 + n * 18);

    for(int i = 1; i <= m; i++) {
        int opt, x, y;
        cin >> opt;
        if(opt == 1) {
            cin >> x >> y;
            dsu.merge(rt[i - 1], rt[i], x, y);
        } else if (opt == 2) {
            cin >> x;
            rt[i] = rt[x];
        } else {
            cin >> x >> y;
            rt[i] = rt[i - 1];
            cout << (dsu.same(rt[i], x, y) ? 1 : 0) << '\n';
        }
    }
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif

    int t = 1;
    // cin >> t;
    while(t--) solve();
	return 0;
}

/*
g++ 1.cpp -std=c++20 -o 1 && 1
*/