记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5;
int a,b,k,opt,root[maxn*20],ls[maxn*20],rs[maxn*20],fa[maxn*20],size[maxn*20],back[maxn*20],n,m,cnt,tot;
void modify(int &now,int pre,int lef,int rig,int to,int aim){
	now=++cnt;
	ls[now]=ls[pre],rs[now]=rs[pre],fa[now]=fa[pre],back[now]=back[pre];
	if(lef==rig){
		fa[now]=aim;
		return;
	}
	int mid=lef+rig>>1;
	if(to<=mid)modify(ls[now],ls[pre],lef,mid,to,aim);
	else modify(rs[now],rs[pre],mid+1,rig,to,aim);
}
void build(int &now,int lef,int rig){
	now=++cnt;
	if(lef==rig){
		fa[now]=now;//faｴ｢ｴ賁ﾐnowｵﾄｸｸﾇﾗ｣ｬ 
		back[now]=lef;//backｽｫnowﾗｪｻｻｳﾉ1ｵｽnｵﾄﾊ 
		return;
	}
	int mid=lef+rig>>1;
	build(ls[now],lef,mid);
	build(rs[now],mid+1,rig);
}
struct edge{
	int fa,size;
};
edge find_fa(int now){
	if(fa[now]==now)return (edge){fa[now],1};
	edge x=find_fa(fa[now]);
	x.size++;
	return x;
}
edge find_place(int now,int lef,int rig,int to){
	if(lef==rig){
		return find_fa(now);
	}
	int mid=lef+rig>>1;
	if(to<=mid)return find_place(ls[now],lef,mid,to);
	else return find_place(rs[now],mid+1,rig,to);
}
void merge(int x,int y){
	edge fa_x=find_place(root[tot],1,n,x),fa_y=find_place(root[tot],1,n,y);
	if(fa_x.size<fa_y.size)swap(fa_x.size,fa_y.size),swap(fa_x.fa,fa_y.fa);//ｱ｣ﾖ､ﾒｻｶｨﾊﾇｽｫyｺﾏｲ｢ｵｽx
	++tot;
	modify(root[tot],root[tot-1],1,n,back[fa_y.fa],fa_x.fa);
}
signed main(){
//	freopen("1.in","r",stdin);
//	freopen("my.out","w",stdout);
	cin>>n>>m;
	build(root[0],1,n);
	for(int i=1;i<=m;i++){
		cin>>opt>>a;
		if(opt==1){
			cin>>b;
			merge(a,b);
		}else{
			if(opt==2){
				root[++tot]=root[a];
			}else{
				cin>>b;
				tot++;
				root[tot]=root[tot-1];
				int fa_a=find_place(root[tot],1,n,a).fa,fa_b=find_place(root[tot],1,n,b).fa;
//				cout<<fa_a<<" "<<fa_b<<"\n";
//				cout<<back[fa_a]<<" "<<back[fa_b]<<"\n";
				if(back[fa_a]==back[fa_b]){
					cout<<"1\n";
				}else cout<<"0\n";
			}
		}
	}
	return 0;
}