深度也加了啊啊啊啊啊啊啊

// Problem: P3402 可持久化并查集
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3402
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <stdio.h>
#include <string.h> 
inline int read()
{
	int num=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>47&&c<58)num=num*10+(c^48),c=getchar();
	return num*f;
}
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
int a[200005];
struct Node{
	Node *lc,*rc;
	int x,sz;
	Node()
	{
		lc=rc=NULL;
		x=0;
	}
	//void qaq(){lc=new Node();rc=new Node();}
};
Node* p[200005];
void build(Node *o,int l,int r)
{
	if(l==r)
	{
		o->x=a[l];
		o->lc=o->rc=NULL;
		o->sz=1;
		return;
	}
	o->lc=new Node();
	o->rc=new Node();
	//o->qaq();
	int m=l+r>>1; 
	build(o->lc,l,m);
	build(o->rc,m+1,r);
}
void add(Node* o,int l,int r,int pos,int x,Node *q,int vvv)
{
	//puts("TESt");//''
	if(l==r)
	{
		o->x=x;
		o->sz=max(o->sz,vvv+1);
		o->lc=o->rc=NULL;
		return;
	}
	int m=l+r>>1;
	if(pos<=m)
	{
		o->lc=new Node();
		add(o->lc,l,m,pos,x,q->lc,vvv);
		o->rc=q->rc;
	}
	else
	{
		o->rc=new Node();
		add(o->rc,m+1,r,pos,x,q->rc,vvv);
		o->lc=q->lc;
	}
}
/*void add1(Node* o,int l,int r,int pos,int x,Node *q)
{
	//puts("TESt");//''
	if(l==r)
	{
		o->sz+=x;
		o->lc=o->rc=NULL;
		return;
	}
	int m=l+r>>1;
	if(pos<=m)
	{
	//	o->lc=new Node();
		add1(o->lc,l,m,pos,x,q->lc);
	//	o->rc=q->rc;
	}
	else
	{
	//	o->rc=new Node();
		add1(o->rc,m+1,r,pos,x,q->rc);
	//	o->lc=q->lc;
	}
}*/
int query(Node *o,int l,int r,int pos)
{
	if(l==r)return o->x;
	int m=l+r>>1;
	return pos<=m?query(o->lc,l,m,pos):query(o->rc,m+1,r,pos);
}
int query1(Node *o,int l,int r,int pos)
{
	if(l==r)return o->sz;
	int m=l+r>>1;
	return pos<=m?query1(o->lc,l,m,pos):query1(o->rc,m+1,r,pos);
}
int m;
inline int fa(int x,int v)
{
	while(1)
	{
		int q=query(p[x],1,m,v);
		if(v==q)return v;
		v=q;
	}
	return 114514;
}
unsigned seed=171487;
inline int rd()
{
	seed^=seed>>5;
	seed^=seed<<13;
	seed^=seed>>7;
	return seed;
}
inline int sz(int x,int v)
{
	return query1(p[x],1,m,v);
}
void del(Node*o)
{
	if(o==NULL)return;
	del(o->lc),del(o->rc);
	delete o;
	o=NULL;
}
int main()
{
	int n=read(),T=read();//p[0]->lc=new Node();
	m=1;while(m<n)m<<=1;m=n;
	for(int i=1;i<=m;i++)a[i]=i;
	p[0]=new Node();
	build(p[0],1,m);
	for(int i=1;i<=T;i++)
	{
		p[i]=new Node();
		int op=read();
		if(op==1)
		{
			int l=read(),r=read();
			//if(rd()&1)l^=r^=l^=r;
			int fl=fa(i-1,l),fr=fa(i-1,r);
			if(fl==fr)
			{
				delete p[i];
				p[i]=p[i-1];
			}
			else 
			{
				int szl=sz(i-1,fl),szr=sz(i-1,fr);
				if(szl>szr)fl^=fr^=fl^=fr,szl^=szr^=szl^=szr;
				//::p[i]=new Node();
				add(p[i],1,m,fr,fl,p[i-1],szl);
				//add1(p[i],1,m,fr,szl,p[i-1]);
			}
		}
		else if(op==2)
		{
			int l=read();
			delete p[i];
			p[i]=p[l];
		}
		else
		{
			int l=read(),r=read();
			int fl=fa(i-1,l),fr=fa(i-1,r);
			if(fl==fr)puts("1");
			else puts("0");
			p[i]=p[i-1];
		}
		/*int v=read(),op=read(),loc=read();
		if(op==1)
		{
			int val=read();
			add(p[i],1,m,loc,val,p[v]);
		}
		else
		{
			printf("%d\n",query(p[v],1,m,loc));
			p[i]=p[v];
		}*/
	}
	//for(int i=0;i<=T;i++)del(p[i]),size::del(size::p[i]);
}