且开不开 O2 差距巨大，是常数问题还是写法问题啊qwq

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;

inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),c=getchar();}
	return x*f;
}

inline void wr(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)wr(x/10);putchar(x%10+'0');
}

const int N=2e5+10,M=5e6+10;
struct seg{
	int ls,rs,fa,dep;
}t[M];
int rt[M],tot;
int n,m;
inline void build(int &p,int l,int r)
{
	if(!p)p=++tot;
	if(l==r){t[p].fa=l;return;}
	int mid=(l+r)>>1;
	build(t[p].ls,l,mid),build(t[p].rs,mid+1,r);
}
inline int query(int p,int l,int r,int x)
{
	if(l==r)return p;
	int mid=(l+r)>>1;
	if(x<=mid)return query(t[p].ls,l,mid,x);
	return query(t[p].rs,mid+1,r,x);
}
inline int find(int rt,int x)
{
	int id=query(rt,1,n,x);
	return x==t[id].fa?id:find(rt,t[id].fa);
}
inline void merge(int &p,int pr,int l,int r,int x,int y)
{
	t[p=++tot]=t[pr];
	if(l==r){t[p].fa=y;return;}
	int mid=(l+r)>>1;
	if(x<=mid)merge(t[p].ls,t[pr].ls,l,mid,x,y);
	else merge(t[p].rs,t[pr].rs,mid+1,r,x,y);
}
inline void upd(int p,int l,int r,int x)
{
	t[p].dep++;if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)upd(t[p].ls,l,mid,x);
	else upd(t[p].rs,mid+1,r,x);
}
int main()
{
	// freopen("P3402_1.in","r",stdin);
	// freopen("P3402_1.out","w",stdout);
	auto st=clock();
	n=read(),m=read();
	build(rt[0],1,n);
	for(int i=1;i<=m;i++)
	{
		int op=read();
		if(op==1)
		{
			int a=read(),b=read();rt[i]=rt[i-1];
			int id1=find(rt[i],a),id2=find(rt[i],b);
			if(id1==id2)continue;	
			if(t[id1].dep>t[id2].dep)swap(id1,id2);
			merge(rt[i],rt[i-1],1,n,t[id1].fa,t[id2].fa);
			if(t[id1].dep==t[id2].dep)upd(rt[i],1,n,t[id2].fa);
		}
		if(op==2)
		{
			int k=read();
			rt[i]=rt[k];
		}
		if(op==3)
		{
			int a=read(),b=read();rt[i]=rt[i-1];
			int id1=find(rt[i],a),id2=find(rt[i],b);
			wr(t[id1].fa==t[id2].fa),puts("");
		}
	}
	auto en=clock();
	cerr<<en-st<<endl;
	return 0;
}