https://www.luogu.com.cn/record/191145002
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int maxn=2e5+10;
const int inf=1e9+10;	
int n,T;
struct TREE{
	int lp[maxn*32],rp[maxn*32],w[maxn*32];
	int root[maxn];
	int a[maxn];
	int cnt=0;
	int sze;
	void build(int &o,int l,int r) {
		o=++cnt;
		if(l==r) {
			w[o]=a[l]; return;
		}
		int mid=(l+r)/2;
		build(lp[o],l,mid);build(rp[o],mid+1,r);
	}
	void update(int &o,int last,int l,int r,int x,int y) {
		o=++cnt;
		lp[o]=lp[last],rp[o]=rp[last],w[o]=w[last];
		if(l==r) {
			w[o]=y;
			return;
		}
		int mid=(l+r)/2;
		if(x<=mid)update(lp[o],lp[last],l,mid,x,y);
		else update(rp[o],rp[last],mid+1,r,x,y);
	}
	int query(int &o,int l,int r,int x) {
		if(l==r) return w[o];
		int mid=(l+r)/2;
		if(x<=mid) return query(lp[o],l,mid,x);
		else return query(rp[o],mid+1,r,x);
	}
	int Q(int x,int v) {
//		cout<<n<<"\n"
		return query(root[v],1,sze,x);
	}
	void C(int x,int y,int v,int last) {
		update(root[v],root[last],1,sze,x,y);
	}
}fa,sze;
int get(int x,int v) {
	int fax=fa.Q(x,v);
	if(x==fax) return x;
	return get(fax,v);
}

void merge(int a,int b,int v) {
	int faa=fa.Q(a,v),fab=fa.Q(b,v);
	if(faa==fab) return;
	int cnta=sze.Q(faa,v),cntb=sze.Q(fab,v);
		
	if(cnta>cntb) {
		fa.C(fab,faa,v,v-1);
		sze.C(faa,cnta+cntb,v,v-1);
	}
	else {
		fa.C(faa,fab,v,v-1);
		sze.C(fab,cnta+cntb,v,v-1);
	}
	
	 
}
signed main() {
	cin.tie(0), cout.tie(0);
	ios::sync_with_stdio(0);

	cin>>n>>T;
	for(int i=1;i<=n;i++) {
		fa.a[i]=i;
		sze.a[i]=1;
	}
	fa.build(fa.root[0],1,n);sze.build(sze.root[0],1,n);
	fa.sze=n,sze.sze=n;
	for(int i=1;i<=T;i++) {
		fa.root[i]=fa.root[i-1];
		sze.root[i]=sze.root[i-1];
		int op,a,b; 
		cin>>op;
		if(op==1) {
			cin>>a>>b;
			merge(a,b,i);
		}
		if(op==2) {
			cin>>a;
			fa.root[i]=fa.root[a];
			sze.root[i]=sze.root[a];
		}
		if(op==3) {
			cin>>a>>b;
			if(get(a,i)==get(b,i)) cout<<1<<"\n";
			else cout<<0<<"\n";
		}
	}
	return 0;
}