样例不过求调，必关注

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,M=N*30;
struct Tree{int l,r,val,siz;}t[M];
int n,m,sz,ro[N];
void build(int &k,int l,int r){
	k=++sz;int mid=(l+r)>>1;
	if(l==r) {t[k].val=l;t[k].siz=1;return;}
	build(t[k].l,l,mid);build(t[k].r,mid+1,r);
}
int nu1,nu2,pos,c1,c2;
void query(int k,int l,int r){
	if(l==r){nu1=t[k].val;nu2=t[k].siz;return;}
	int mid=(l+r)>>1;
	if(pos<=mid) query(t[k].l,l,mid);else query(t[k].r,mid+1,r);
}
void inser(int &k,int pre,int l,int r){
	k=++sz;t[k]=t[pre];int mid=(l+r)>>1;
	if(l==r){if(c1) t[k].val=c1;if(c2) t[k].siz=c2;return;}
	if(pos<=mid) inser(t[k].l,t[pre].l,l,mid);else inser(t[k].r,t[pre].r,mid+1,r); 
}
int fin(int k,int x){
	pos=x;query(ro[k],1,n);int fa=nu1;
	if(fa==x) return x;
	return fin(k,fa);
}
void merge(int k,int a,int b){
	int sa,sb,fa=fin(k,a),fb=fin(k,b);
	pos=fa;query(ro[k],1,n);sa=nu2;
	pos=fb;query(ro[k],1,n);sb=nu2;
	if(sa<sb) swap(sa,sb),swap(fa,fb);
	c1=0;c2=sa+sb;pos=fa;inser(ro[k],ro[k],1,n);
	c1=fa;c2=0;pos=sb;inser(ro[k],ro[k],1,n);
}
signed main(){
	scanf("%lld%lld",&n,&m);
    build(ro[0],1,n);
    int opt,a,b,k;
    for(int i=1;i<=m;i++){
        scanf("%lld",&opt);
        if(opt==1){
            ro[i]=ro[i-1];
            scanf("%lld%lld",&a,&b);
            merge(i,a,b);
        }
        else if(opt==2){
            scanf("%lld",&k);
            ro[i]=ro[k];
        }
        else{
            ro[i]=ro[i-1];
            scanf("%lld%lld",&a,&b);
            int fa=fin(i,a),fb=fin(i,b);
            if(fa==fb)printf("1\n");
            else printf("0\n");
        }
    }
	return 0;
}