#include<bits/stdc++.h>
#define ls tree[i].lss
#define rs tree[i].rss
//#define int long long
using namespace std;
int n,m;
int a[(int)1e7];
int rt[(int)1e7],cnt;
struct ccc{
	int fa,lss,rss,dep;
}tree[(int)1e6*30];
int copy(int old){
	tree[++cnt]=tree[old];
	return cnt;
}
int build(int i,int l,int r){
	i=++cnt;
	if(l==r){
		tree[i].fa=l;
		tree[i].dep=1;
		return i;
	}
	int mid=(l+r)>>1;
	ls=build(ls,l,mid);
	rs=build(rs,mid+1,r);
	return i;
}
int id(int i,int l,int r,int x){
	if(l==r)return i;int mid=(l+r)>>1;
	if(x<=mid)return id(ls,l,mid,x);
	else return id(rs,mid+1,r,x);
}
int get(int x,int idx,int r){
	if(tree[idx].fa==x)return x;
	return get(tree[idx].fa,id(r,1,n,tree[idx].fa),r);
}
int merge(int i,int l,int r,int x,int y){
	i=copy(i);
	if(l==r){
		tree[i].fa=y;
		return i;
	}
	int mid=(l+r)>>1;
	if(x<=mid)ls=merge(ls,l,mid,x,y);
	else rs=merge(rs,mid+1,r,x,y);
	return i;
}
int add(int i,int l,int r,int x){
	i=copy(i);
	if(l==r){
		tree[i].dep++;
		return i;
	}
	int mid=(l+r)>>1;
	if(x<=mid)ls=add(ls,l,mid,x);
	else rs=add(rs,mid+1,r,x);
	return i;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	rt[0]=build(0,1,n);
	for(int i=1;i<=m;i++){
		int opt;
		cin>>opt;
		if(opt==1){
			int a,b;
			cin>>a>>b;
			rt[i]=rt[i-1];
			int Fa=get(a,id(rt[i],1,n,a),rt[i]),Fb=get(b,id(rt[i],1,n,b),rt[i]);
			int ida=id(rt[i],1,n,Fa),idb=(rt[i],1,n,Fb);
			if(Fa==Fb)continue;
			if(tree[ida].dep>tree[idb].dep)swap(Fa,Fb);
			rt[i]=merge(rt[i],1,n,Fa,Fb);
			if(tree[ida].dep==tree[idb].dep)rt[i]=add(rt[i],1,n,Fa);
		}
		if(opt==2){
			int k;
			cin>>k;
			rt[i]=rt[k];
		}
		if(opt==3){
			int a,b;
			cin>>a>>b;
			rt[i]=rt[i-1];
			int Fa=get(a,id(rt[i],1,n,a),rt[i]),Fb=get(b,id(rt[i],1,n,b),rt[i]);
			if(Fa==Fb)puts("1");
			else puts("0");
		}
	}
	return 0;
}

记录