#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct node
{
	int lson,rson,fa,deep;
}a[maxn*25];
int n,m,top,root[maxn];
inline int build(int l,int r)
{
	int num=++top;
	if(l==r)
	{
		a[num].fa=l;
		return num;
	}
	int mid=l+r>>1;
	a[num].lson=build(l,mid);
	a[num].rson=build(mid+1,r);
	return num;
}
inline int query(int now,int l,int r,int x)
{
	if(l==r)return now;
	int mid=l+r>>1;
//	cout<<"<<<"<<now<<" "<<a[now].lson<<endl;
	if(mid>=x)return query(a[now].lson,l,mid,x);
	else return query(a[now].rson,mid+1,r,x);
}
inline int find(int x,int num)
{
	int fa=query(root[x],1,n,num);
	if(a[fa].fa==num)return fa;
	return find(x,a[fa].fa); 
}
inline int clone(int x)
{
	int num=++top;
	a[num]=a[x];
	return num;
}
inline int hb(int x,int l,int r,int fx,int fy)
{
	int num=clone(x);
//	cout<<"hb:"<<a[x].rson<<" "<<x<<" "<<l<<" "<<r<<" "<<fx<<" "<<fy<<endl;
	if(l==r)
	{
		a[num].fa=fy;
		return num;
	}
	int mid=l+r>>1;
//	cout<<"mid="<<mid<<endl;
	if(mid>=fx)
	{
//		cout<<"left"<<endl;
		a[num].lson=hb(a[x].lson,l,mid,fx,fy);
	}
	else a[num].rson=hb(a[x].rson,mid+1,r,fx,fy);
	return num;
}
inline int add(int x,int l,int r,int xx)
{
	int num=clone(x);
//	cout<<"###"<<x<<" "<<a[x].lson<<" "<<a[x].rson<<endl;
	if(l==r)
	{
		++a[num].deep;
		return num;
	}
	int mid=l+r>>1;
	if(mid>=x)a[num].lson=add(a[x].lson,l,mid,xx);
	else a[num].rson=add(a[x].rson,mid+1,r,xx);
	return num;
}
inline void merge(int x,int xx,int yy)
{
	root[x]=root[x-1];
	xx=find(x,xx),yy=find(x,yy);
	if(a[xx].fa!=a[yy].fa)
	{
		if(a[xx].deep>a[yy].deep)swap(xx,yy);
		root[x]=hb(root[x-1],1,n,a[xx].fa,a[yy].fa);
//		cout<<"a[1].lson="<<a[1].lson<<endl;
		if(a[xx].deep==a[yy].deep)root[x]=add(root[x],1,n,a[yy].fa);
	}
}
inline bool check(int x,int xx,int yy)
{
	xx=find(x,xx),yy=find(x,yy);
	if(a[xx].fa==a[yy].fa)return 1;
	return 0;
}
int main()
{
	n=read(),m=read();
	root[0]=build(1,n);
	int op,a,b;
	for(int i=1;i<=m;i++)
	{
		op=read(),a=read();
		if(op==1)
		{
			b=read();
			merge(i,a,b);
		}
		if(op==2)root[i]=root[a];
		if(op==3)
		{
			b=read();
			if(check(i-1,a,b))putchar('1');
			else putchar('0');
			putchar('\n');
			root[i]=root[i-1]; 
		}
	}
}

在op==3的时候很慢。