代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=200009;
int a[N],n,m;
template <class T> bool read(T &r) {
	r = 0; static char ch = getchar(); bool f = false;
	while (ch < 48 || ch > 57) { if (ch == EOF) return true; if (ch == 45) f ^= 1; ch = getchar(); }
	while (ch >= 48 && ch <= 57) { r = r * 10 + ch - 48; ch = getchar(); }
	if (f) r = -r; return false;
}
template <class T> void write(T w, char end = '\n') {
	static char write_buf[55]; char *pos = write_buf;
	if (w == 0) { putchar('0'); putchar(end); return; }
	if (w < 0) { putchar('-'); w = -w; }
	while (w) {
		*(pos++) = w % 10 + '0';
		w /= 10;
	}
	while (pos != write_buf) putchar(*(--pos));
	putchar(end);
}
int root[N],cnt,cnt1;
struct Node
{
	int l,r,lch,rch,val,sz;
}f[N<<5];
int build(int l,int r)
{
	if(l==r) return f[++cnt]=Node{l,r,0,0,l,1},cnt;
	else
	{
		int nw=++cnt;
		f[nw]=Node{l,r,build(l,l+r>>1),build((l+r>>1)+1,r),0,0};
		return nw;
	}
}
int update(int num,int x,int y,int z)
{
	if(f[num].l==f[num].r)
	{
		f[++cnt]=Node{f[num].l,f[num].r,0,0,y,z};
		return cnt;
	}
	else
	{
		if(x<=f[f[num].lch].r)
		{
			int nw=++cnt;
			f[nw]=Node{f[num].l,f[num].r,update(f[num].lch,x,y,z),f[num].rch,0,0};
			return nw;
		}
		else
		{
			int nw=++cnt;
			f[nw]=Node{f[num].l,f[num].r,f[num].lch,update(f[num].rch,x,y,z),0,0};
			return nw;
		}
	}
}
int query(int num,int x)
{
	if(f[num].l==f[num].r)
	{
		return f[num].val;
	}
	else
	{
		if(x<=f[f[num].lch].r)
		{
			return query(f[num].lch,x);
		}
		else
		{
			return query(f[num].rch,x);
		}
	}
}
int query1(int num,int x)
{
	if(f[num].l==f[num].r)
	{
		return f[num].sz;
	}
	else
	{
		if(x<=f[f[num].lch].r)
		{
			return query1(f[num].lch,x);
		}
		else
		{
			return query1(f[num].rch,x);
		}
	}
}
int find(int x,int y)
{
	int q=query(root[y],x);
	return q==x?q:find(q,y);
}
void uni(int x,int y,int z,int w)
{
	x=find(x,z),y=find(y,z);
	int qx=query1(root[z],x),qy=query1(root[z],y);
	if(qx>qy) swap(x,y),swap(qx,qy);
	root[w]=update(root[z],x,y,max(qy,qx+1));
}
int main()
{
//		freopen("P3402_1.in","r",stdin);
//		freopen("P3402.out","w",stdout);
	scanf("%d%d",&n,&m);
	root[0]=build(1,n);
	//	cerr<<clock();
	for(int i=1,x,y,opt;i<=m;i++)
	{
		read(opt),read(x);
		if(opt==1)
		{
			read(y);
			uni(x,y,i-1,i);
		}
		else if(opt==2)
		{
			root[i]=root[x];
		}
		else
		{
			read(y);
			write(find(x,i-1)==find(y,i-1));
			root[i]=root[i-1];
		}
	}
}