#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N=2e5+5,M=8e6+5;
int n,m,rt[N],ls[M],rs[M],fa[M],sz[M],cnt;
il int read(){ 
	int f=1,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=x*10+s-'0';
		s=getchar();
	}
	return x*f;
}
il void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);	
	putchar(x%10+'0');
}
il void build(int &x,int l,int r){
	if(!x) x=++cnt;
	if(l==r){
		fa[x]=l;
		sz[x]=1;
		return;
	}
	int mid=(l+r)/2;
	build(ls[x],l,mid);
	build(rs[x],mid+1,r);
}
il int get_fa(int x,int l,int r,int h){
	if(l==r) return fa[x];
	int mid=(l+r)/2;
	if(h<=mid) return get_fa(ls[x],l,mid,h);
	return get_fa(rs[x],mid+1,r,h);
}
il int find(int rt,int x){
	int fa=get_fa(rt,1,n,x);
	if(fa==x) return x;
	return find(rt,fa);
}
il int query_sz(int x,int l,int r,int h){
	if(l==r) return sz[x];
	int mid=(l+r)/2;
	if(h<=mid) return query_sz(ls[x],l,mid,h);
	return query_sz(rs[x],mid+1,r,h);
}
il void modify_fa(int sto,int &x,int l,int r,int h,int v){
	if(!x) x=++cnt;
	if(l==r){
		fa[x]=v;
		return;
	}
	int mid=(l+r)/2;
	if(h<=mid){
		rs[x]=rs[sto];
		modify_fa(ls[sto],ls[x],l,mid,h,v);
	}
	else{
		ls[x]=ls[sto];
		modify_fa(rs[sto],rs[x],mid+1,r,h,v);
	}
}
il void modify_sz(int sto,int &x,int l,int r,int h,int v){
	if(!x) x=++cnt;
	if(l==r){
		fa[x]=fa[sto];
		sz[x]=sz[sto]+v;
		return;
	}
	int mid=(l+r)/2;
	if(h<=mid){
		rs[x]=rs[sto];
		modify_sz(ls[sto],ls[x],l,mid,h,v);
	}
	else{
		ls[x]=ls[sto];
		modify_sz(rs[sto],rs[x],mid+1,r,h,v);	
	}
}
int main(){
	n=read(),m=read();
	build(rt[0],1,n);
	for(int i=1,opt,x,y;i<=m;i++){
		opt=read();
		if(opt==1){
			x=find(rt[i-1],read());
			y=find(rt[i-1],read());
			if(x!=y){
				int szx=query_sz(rt[i-1],1,n,x),szy=query_sz(rt[i-1],1,n,y);
				if(szx>szy) swap(x,y);
				int tmp=0;
				modify_fa(rt[i-1],tmp,1,n,x,y);
				modify_sz(tmp,rt[i],1,n,y,szx+szy);
			}
			else rt[i]=rt[i-1]; 
		}
		else if(opt==2) rt[i]=rt[read()];
		else{
			rt[i]=rt[i-1];
			puts(find(rt[i],read())==find(rt[i],read())?"1":"0");
		}
	}
	return 0;
}