RT，代码如下

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 200050
using namespace std;
struct xds{
	int lz,rz,l,r,fa,sd;
}yd[N*45];
int n,m,cnt,rt[N],dc;
void js(int &b,int l,int r){
	b=++cnt;
	yd[b].l=l,yd[b].r=r;
	if(l==r){
		yd[b].fa=l;
		yd[b].sd=1;
		return ;
	}
	int mid=(l+r)>>1;
	js(yd[b].lz,l,mid);
	js(yd[b].rz,mid+1,r);
}
int md(int b){
	int bb=++cnt;
	yd[bb]=yd[b];
	return bb;
}
int gf(int b,int x,int z){
	if(b<=dc)b=md(b);
	if(yd[b].l==yd[b].r){
		yd[b].fa=z;
		return b;
	}
	int mid=(yd[b].l+yd[b].r)>>1;
	if(mid>=x)yd[b].lz=gf(yd[b].lz,x,z);
	else yd[b].rz=gf(yd[b].rz,x,z);
	return b;
}
int gg(int b,int x,int z){
	if(b<=dc)b=md(b);
	if(yd[b].l==yd[b].r){
		yd[b].sd=z;
		return b;
	}
	int mid=(yd[b].l+yd[b].r)>>1;
	if(mid>=x)yd[b].lz=gg(yd[b].lz,x,z);
	else yd[b].rz=gg(yd[b].rz,x,z);
	return b;
}
int cf(int b,int x){
	if(yd[b].l==yd[b].r){
		return yd[b].fa;
	}
	int mid=(yd[b].l+yd[b].r)>>1;
	if(mid>=x)return cf(yd[b].lz,x);
	else return cf(yd[b].rz,x);
}
int cs(int b,int x){
	if(yd[b].l==yd[b].r){
		return yd[b].fa;
	}
	int mid=(yd[b].l+yd[b].r)>>1;
	if(mid>=x)return cs(yd[b].lz,x);
	else return cs(yd[b].rz,x);
}
int zbb(int ddd,int x){
	while(cs(rt[ddd],x)!=x)x=cs(rt[ddd],x);
	return x;
}
void hb(int ddd,int x,int y){
	int xb=zbb(ddd,x),yb=zbb(ddd,y);
	if(xb==yb)return;
	int sx=cs(rt[ddd],xb),sy=cs(rt[ddd],yb);
	if(sx<sy) rt[ddd]=gf(rt[ddd],xb,yb);
	else rt[ddd]=gf(rt[ddd],yb,xb);
	gg(rt[ddd],yb,sy+1);
}
int read(){
	char c=getchar();
	int s=0;
	while(c<'0'&&c<'9')c=getchar();
	while(c>='0'&&c<='9'){
		s=s*10+c-'0';
		c=getchar();
	}
	return s;
}
int main(){
	n=read();m=read();
	js(rt[0],1,n);
	int aa,bb,cc,dd=0;
	for(int i=1;i<=m;i++){
		dc=cnt;
		aa=read(),bb=read();
		rt[i]=rt[i-1];
		if(aa==2){
			rt[i]=rt[bb];
		}
		else{
			cc=read();
			if(aa==1){
				hb(i,bb,cc);
			}
			else{
				int xb=zbb(i-1,bb),yb=zbb(i-1,cc);
				if(xb!=yb){
					puts("0");
				}
				else{
					puts("1");
				}
			}
		}
	}
	return 0;
}