#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5,M=2e5+5,L=5e6+5;
int n,m,root[M],idx;
struct nnd{
	int ls,rs;
	int fa,sum;
}tree[L];

void build_tree(const int& p,const int& l,const int& r){
	idx++;
	if(l==r){
		tree[p].sum=1;
		tree[p].fa=l;
		return;
	}
	int ls=p<<1,rs=ls|1,mid=l+r>>1;
	tree[p].ls=ls,tree[p].rs=rs;
	build_tree(ls,l,mid);
	build_tree(rs,mid+1,r);
}
void change_fa(int& p,const int& pc,const int& x,const int& z,const int& l,const int& r){
	if(!p)p=++idx;
	if(l==r){
		tree[p].fa=z;
		tree[p].sum=tree[pc].sum;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid){
		if(!tree[p].rs)tree[p].rs=tree[pc].rs;
		change_fa(tree[p].ls,tree[pc].ls,x,z,l,mid);
	} else {
		if(!tree[p].ls)tree[p].ls=tree[pc].ls;
		change_fa(tree[p].rs,tree[pc].rs,x,z,mid+1,r);
	}
}
void change_sum(int& p,const int& pc,const int& x,const int& z,const int& l,const int& r){
	if(!p)p=++idx;
	if(l==r){
		tree[p].sum=tree[pc].sum+z;
		tree[p].fa=tree[pc].fa;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid){
		if(!tree[p].rs)tree[p].rs=tree[pc].rs;
		change_sum(tree[p].ls,tree[pc].ls,x,z,l,mid);
	} else {
		if(!tree[p].ls)tree[p].ls=tree[pc].ls;
		change_sum(tree[p].rs,tree[pc].rs,x,z,mid+1,r);
	}
}
int get_fa(const int& p,const int& x,const int& l,const int& r){
	if(l==r){
		return tree[p].fa;
	}
	int mid=l+r>>1;
	if(x<=mid){
		return get_fa(tree[p].ls,x,l,mid);
	} else {
		return get_fa(tree[p].rs,x,mid+1,r);
	}
}
int get_sum(const int& p,const int& x,const int& l,const int& r){
	if(l==r){
		return tree[p].sum;
	}
	int mid=l+r>>1;
	if(x<=mid){
		return get_sum(tree[p].ls,x,l,mid);
	} else {
		return get_sum(tree[p].rs,x,mid+1,r);
	}
}
int find(const int& x,const int& rt){
	int fa=get_fa(rt,x,1,n);
	if(fa==x)return x;
	else return find(fa,rt);
}

int main(){
	freopen("001.in","r",stdin);
	freopen("001.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	cin>>n>>m;
//	cout<<n<<" "<<m<<"\n";
	root[0]=1;
	build_tree(1,1,n);
	int c,x,y;
	for(int i=1;i<=m;i++){
		cin>>c;
		if(c==1){
//			cout<<"111\n";
			cin>>x>>y;
			int fx=find(x,root[i-1]);
			int fy=find(y,root[i-1]);
			int sumx=get_sum(root[i-1],fx,1,n);
			int sumy=get_sum(root[i-1],fy,1,n);
			if(fx==fy){
				root[i]=root[i-1];
				continue;
			}
			if(sumx>=sumy){
				change_fa(root[i],root[i-1],fy,fx,1,n);
				change_sum(root[i],root[i-1],fx,sumy,1,n);
			} else {
				change_fa(root[i],root[i-1],fx,fy,1,n);
				change_sum(root[i],root[i-1],fy,sumx,1,n);
			}
		}
		if(c==2){
			cin>>x;
			root[i]=root[x];
		}
		if(c==3){
			cin>>x>>y;
			int fx=find(x,root[i-1]);
			int fy=find(y,root[i-1]);
//			cout<<x<<" "<<y<<" ";
			if(fx==fy){
				cout<<"1\n";
			} else {
				cout<<"0\n"; 
			}
			root[i]=root[i-1];
		}
	} 
}