#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define qwq 100007
inline int read() 
{
	register int x=0,o=0;char ch=getchar();
	while(ch!='-'&&(ch<'0'||'9'<ch)) ch=getchar();
	if(ch=='-') o=1,ch=getchar();
	while('0'<=ch&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return o?-x:x;
}
int n,m;
struct tree{
	int l_son,r_son;
	int fa;
	int deep;
}tr[qwq<<5];
int count,root[qwq<<1];
inline void build(int l,int r,int cnt){
	if(l==r){
		tr[cnt].fa=l;
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,tr[cnt].l_son=++count);
	build(mid+1,r,tr[cnt].r_son=++count);
	return ;
}
inline void change(int last_cnt,int cnt,int l,int r,int v,int f){
	if(l==r){
		tr[cnt].fa=f;
		tr[cnt].deep=tr[last_cnt].deep;
		return ;
	}
	int mid=(l+r)>>1;
	if(v<=mid)tr[cnt].r_son=tr[last_cnt].r_son,change(tr[last_cnt].l_son,tr[cnt].l_son=++count,l,mid,v,f);
	else tr[cnt].l_son=tr[last_cnt].l_son,change(tr[last_cnt].r_son,tr[cnt].r_son=++count,mid+1,r,v,f);
	return ;
}
inline void change_deep(int cnt,int l,int r,int v){
	if(l==r){
		++tr[cnt].deep;
		return ;
	}
	int mid=(l+r)>>1;
	if(v<=mid)change_deep(tr[cnt].l_son,l,mid,v);
	else change_deep(tr[cnt].r_son,mid+1,r,v);
	return ; 
}
inline int where(int cnt,int l,int r,int v){
	if(l==r){
		return cnt;
	}
	int mid=(l+r)>>1;
	if(v<=mid)return where(tr[cnt].l_son,l,mid,v);
	else return where(tr[cnt].r_son,mid+1,r,v);
}
inline int find_f(int root,int v){
	int cnt=where(root,1,n,v);
	if(tr[cnt].fa==v)return cnt;
	return find_f(root,tr[cnt].fa);
}
inline void add(int last_root,int i,int x,int y){
	x=find_f(root[i],x);y=find_f(root[i],y);
	if(tr[x].fa==tr[y].fa)return ;
	if(tr[x].deep>tr[y].deep)std::swap(x,y);
	change(last_root,root[i]=++count,1,n,tr[x].fa,tr[y].fa);
	if(tr[x].deep==tr[y].deep)change_deep(root[i],1,n,tr[x].fa);
	return ;
}
inline int is_same_set(int root,int x,int y){
	x=find_f(root,x);y=find_f(root,y);
	return tr[x].fa==tr[y].fa;
}
int main(){
//	freopen("q.txt","r",stdin);
//	freopen("a.txt","w",stdout);
	n=read();m=read();
	build(1,n,root[0]=++count);
	for(register int i=1;i<=m;++i){
		register int q,a,b;
		q=read();
		if(q==1){
			root[i]=root[i-1];
			a=read();b=read();
			add(root[i-1],i,a,b);
		}
		if(q==2){
			a=read();
			root[i]=root[a];
		}
		if(q==3){
			root[i]=root[i-1];
			a=read();b=read();
			printf("%d\n",is_same_set(root[i],a,b));
		}
	}
	return 0;
}

本机跑2s多/kk有没有神仙能帮我康康是复杂度退化还是人傻常数大啊zbl