题目链接
主席树叶子节点维护fa数组，每次的修改操作只会改变一个叶子结点的fa值，所以考虑动态开点。合并的时候启发式合并就行了。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
#define all(c) ((c).begin()), ((c).end())
#define mp(a, b) make_pair(a, b)
#define pb(x) push_back(x)
template<typename T>T gcd(T a, T b) {return b==0?a:gcd(b, a%b);}
#ifndef ONLINE_JUDGE
#define debug(fmt, ...) {printf("debug ");printf(fmt,##__VA_ARGS__);puts("");}
#else
#define debug(fmt, ...)
#endif
const int maxn = 4e5+5;
typedef long long ll;
const ll mod = 1e9+7;
int Case = 1;
int n, m, tot;
int ch[maxn<<5][2], fa[maxn<<5], root[maxn<<5], dep[maxn<<5];
int newnode() {
    tot++;
    ch[tot][0] = ch[tot][1] = 0;
    return tot;
}
void build(int &rt, int l, int r) {
    rt = newnode();
    if(l == r) {fa[rt] = l;dep[rt] = 1;return;}
    int mid = (l+r)/2;
    build(ch[rt][0], l, mid);
    build(ch[rt][1], mid+1, r);
}
void insert(int &rt, int tc, int l, int r, int ida, int idb) {
    rt = newnode();
    ch[rt][1] = ch[tc][1];ch[rt][0] = ch[tc][0];
    if(l == r) {
        fa[rt] = fa[idb];
        dep[rt] = dep[idb];
        if(dep[ida] == dep[idb]) dep[rt]++;
        return;
    }
    int mid = (l+r)/2;
    if(fa[ida] <= mid) insert(ch[rt][0], ch[tc][0], l, mid, ida, idb);
    else insert(ch[rt][1], ch[tc][1], mid+1, r, ida, idb);
}
int query(int rt, int l, int r, int pos) {
    if(l == r) return rt;
    int mid = (l+r)/2;
    if(pos <= mid) return query(ch[rt][0], l, mid, pos);
    else return query(ch[rt][1], mid+1, r, pos);
}
int find(int i, int x) {
    int rt = query(root[i], 1, n, x);
    while(fa[rt] != x) {
        x = fa[rt];
        rt = query(root[i], 1, n, fa[rt]);
    }
    return rt;
}
void _union(int i, int x, int y) {
    int fx = find(i, x), fy = find(i, y);
    if(fa[fx] == fa[fy]) return;
    if(dep[fx] > dep[fy]) insert(root[i], root[i-1], 1, n, fx, fy);
    else insert(root[i], root[i-1], 1, n, fy, fx);
}
void solve() {
    cin>>n>>m;int last = 0;
    build(root[0], 1, n);
    for(int i = 1; i <= m; i++) {
        int op, a, b, k;cin>>op;
        if(op == 1) {
            root[i] = root[i-1];
            cin>>a>>b;
            a ^= last;b ^= last;
            _union(i, a, b);
        }
        else if(op == 2) {
            cin>>k;k ^= last;root[i] = root[k];
        }
        else {
            root[i] = root[i-1];
            cin>>a>>b;
            a ^= last;b ^= last;
            cout<<(last = (fa[find(i, a)] == fa[find(i, b)]))<<endl;
        }
    }
    return;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    while(Case--) {
        solve();
    }
    return 0;
}