#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
#define midd() unsigned mid(l+r>>1)
using namespace std;
const unsigned N(2e5+1);
unsigned n,cnt,tot,rt_d[N],rt_f[N];
struct Node{
	unsigned ls,rs,val;
}hjt[40*N];
inline void read(unsigned &x){
	x=0;
char ch;
for(ch=getchar();ch<48||ch>57;ch=getchar());
x=ch-48;
for(ch=getchar();ch>=48&&ch<=57;ch=getchar())
x=(x<<1)+(x<<3)+ch-48;
return ;
}
void chnge(unsigned l,unsigned r,unsigned lst,unsigned &nw,unsigned p,unsigned val)
{
	hjt[nw=++cnt]=hjt[lst];
	if(l==r)
	{
		hjt[nw].val=val;
		return ;
	}
	midd();
	if(p<=mid)return chnge(l,mid,hjt[lst].ls,hjt[nw].ls,p,val);
	return chnge(mid+1,r,hjt[lst].rs,hjt[nw].rs,p,val);
}
unsigned query(unsigned l,unsigned r,unsigned nw,unsigned p)
{
	if(l==r)return hjt[nw].val;
	midd();
	if(mid>=p)
	return query(l,mid,hjt[nw].ls,p);
	return query(mid+1,r,hjt[nw].rs,p);
}
unsigned fnd(unsigned i,unsigned x)
{
	unsigned fx=query(1,n,rt_f[i],x);
	return fx^x?fnd(i,fx):x;
}
inline void mer(unsigned i,unsigned x,unsigned y)
{
	unsigned fx=fnd(i-1,x),fy=fnd(i-1,y),dx=query(1,n,rt_d[i-1],fx),dy=query(1,n,rt_d[i-1],fy);
	if(fx==fy)
	{
		rt_f[i]=rt_f[i-1];
		rt_d[i]=rt_d[i-1];
		return ;
	}
	if(dx>dy)return chnge(1,n,rt_f[i-1],rt_f[i],fy,fx);
	if(dx<dy)return chnge(1,n,rt_f[i-1],rt_f[i],fx,fy);
	chnge(1,n,rt_f[i-1],rt_f[i],fy,fx);
	chnge(1,n,rt_d[i-1],rt_d[i],fx,dx+1);
	return ;
}
void build(unsigned l,unsigned r,unsigned &nw)
{
	nw=++cnt;
	if(l==r)
	{
		hjt[nw].val=++tot;
		return ;
	}
	midd();
	build(l,mid,hjt[nw].ls);
	build(mid+1,r,hjt[nw].rs);
	return ;
}
inline unsigned bol(unsigned i,unsigned x,unsigned y)
{
	return fnd(i-1,x)==fnd(i-1,y)?1:0;
}
int main()
{
	unsigned m;
	register unsigned i,j,d,x,y;
//	scanf("%d%d",&n,&m);
	read(n),read(m);
	build(1,n,rt_f[0]);
	for(i=1;i<=m;i++)
	{
	//	scanf("%d%d",&d,&x);
	read(d),read(x);
		if(d==1)
		{
			//scanf("%d",&y);
			read(y);
			mer(i,x,y);
		}
		else if(d==2)rt_f[i]=rt_f[x],rt_d[i]=rt_d[x];
		else {
		//	scanf("%d",&y);
			read(y);
			rt_f[i]=rt_f[i-1];
			rt_d[i]=rt_d[i-1];
			printf("%d\n",bol(i,x,y));
		}
	}
	return 0;
}