以下是代码

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#define N 100050
#define ll long long
using namespace std;
struct xds{
	ll lz,rz,l,r,fa,sd;
}yd[N*45];
ll n,m,cnt,rt[N],dc;
void js(ll &b,ll l,ll r){
	b=++cnt;
	yd[b].l=l,yd[b].r=r;
	if(l==r){
		yd[b].fa=l;
		return ;
	}
	ll mid=(l+r)>>1;
	js(yd[b].lz,l,mid);
	js(yd[b].rz,mid+1,r);
}
ll md(ll b){
	ll bb=++cnt;
	yd[bb]=yd[b];
	return bb;
}
ll gf(ll b,ll x,ll z){
	if(b<=dc)b=md(b);
	if(yd[b].l==yd[b].r){
		yd[b].fa=z;
		return b;
	}
	ll 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;
}
ll gg(ll b,ll x,ll z){
	if(b<=dc)b=md(b);
	if(yd[b].l==yd[b].r){
		yd[b].sd=z;
		return b;
	}
	ll 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;
}
ll cf(ll b,ll x){
	if(yd[b].l==yd[b].r){
		return yd[b].fa;
	}
	ll mid=(yd[b].l+yd[b].r)>>1;
	if(mid>=x)return cf(yd[b].lz,x);
	else return cf(yd[b].rz,x);
}
ll cs(ll b,ll x){
	if(yd[b].l==yd[b].r){
		return yd[b].fa;
	}
	ll mid=(yd[b].l+yd[b].r)>>1;
	if(mid>=x)return cs(yd[b].lz,x);
	else return cs(yd[b].rz,x);
}
ll zbb(ll ddd,ll x){
	while(cs(rt[ddd],x)!=x)x=cs(rt[ddd],x);
	return x;
}
ll hb(ll ddd,ll x,ll y){
	ll xb=zbb(rt[ddd-1],x),yb=zbb(rt[ddd-1],y);
	ll sx=cs(rt[ddd-1],xb),sy=cs(rt[ddd-1],yb);
	if(sx==sy){
		gg(rt[ddd-1],y,sy+1);
		rt[ddd]=gf(rt[ddd-1],x,y);
	}
	else{
		if(sx<sy) rt[ddd]=gf(rt[ddd-1],x,y);
		else rt[ddd]=gf(rt[ddd],y,x);
	}
}
int main(){
	scanf("%lld%lld",&n,&m);
	js(rt[0],1,n);
	ll aa,bb,cc,dd=0;
	for(ll i=1;i<=m;i++){
		dc=cnt;
		scanf("%lld%lld",&aa,&bb);
		if(aa==2){
			rt[i]=rt[bb];
		}
		else{
			scanf("%lld",&cc);
			if(aa==1){
				hb(i,bb,cc);
			}
			else{
				ll xb=zbb(i-1,bb),yb=zbb(i-1,cc);
				if(xb!=yb){
					printf("0\n");
				}
				else{
					printf("1\n");
				}
			}
		}
	}
	return 0;
}