rt，默默地把24pt调到了72pt，还是T了两个点，但是对比之后实在找不到复杂度挂掉的地方orz请julao们educate

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(register int i = (a);i <= (b);++i)
#define per(i,a,b) for(register int i = (a);i >= (b);--i)  
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;

const int N = 1e5+10;
int n,m,a[2*N],opt,tot,FLAG;

struct node{
    int l,r,fa,deep,num;
    node * ls, * rs;
}Tree[32*N],*root[4*N];

inline node * create(){return &Tree[++tot];}

inline void copy(node * u , node * v){
    u->l = v->l , u->r = v->r;
    u->ls = v->ls , u->rs = v->rs;
    u->fa = v->fa , u->num = v->num , u->deep = v->deep;
    return;
}

inline void build(node * cur,int l,int r){
    cur->l = l , cur->r = r;
    if(l == r){
        cur->fa = cur->num = l , cur->deep = 1;
        return;
    }
    int mid = (l+r)>>1;
    cur->ls = create() , cur->rs = create();
    build(cur->ls,l,mid) , build(cur->rs,mid+1,r);
    return;
}

inline node * upd(node * cur,int x,int F,int D){
    node * now = create();
    copy(now,cur);
    if(cur->l == cur->r){
        now->fa = F;
        now->deep = D + FLAG;
        return now;
    }
    if(cur->l <= x && x <= cur->ls->r) now->ls = upd(cur->ls,x,F,D);
    if(cur->rs->l <= x && x <= cur->r) now->rs = upd(cur->rs,x,F,D);
    return now;
}

inline node * find(node * cur,int x){
    if(cur->l == cur->r) return cur; 
    if(x <= cur->ls->r) return find(cur->ls,x);
    if(x >= cur->rs->l) return find(cur->rs,x);
    return 0;
}

inline node * get_fa(node * cur,int x){
    node * now = find(cur,x);
    if(x == now->fa) return now;
    else return get_fa(cur,now->fa);
}

int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("in.in", "r", stdin);
    freopen("out.out","w",stdout);
    int x,y,F,D,f;
    cin >> n >> m;
    root[0] = create();
    build(root[0],1,n);
    rep(i,1,m){
        cin >> opt;
        if(opt == 1){
            cin >> x >> y;
            node * px = get_fa(root[i-1],x) ,* py = get_fa(root[i-1],y);
            if(px == py){
				root[i] = root[i-1];
				continue;
			}
            if(px->deep > py->deep) F = px->fa , D = px->deep , f = py->fa;
            else F = py->fa , D = py->deep , f = px->fa;
            if(px->deep == py->deep) FLAG = 1;
            else FLAG = 0;
            root[i] = upd(root[i-1],f,F,D);
        } else if(opt == 2){
            cin >> x;
            root[i] = root[x];
        } else {
            root[i] = root[i-1];
            cin >> x >> y;
            node * px = get_fa(root[i],x) ,* py = get_fa(root[i],y);
            if(px->fa == py->fa) cout << "1\n";
            else cout << "0\n";
        }
    }
    return 0;
}