一直有两个点TLE，已经写了按秩合并，还是爆了，果然人菜常数大

求修改……

#include<bits/stdc++.h>
namespace my_std{
	using namespace std;
	#define sz 100020
	#define mod 998244353
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define v edge[i].t
	typedef long long ll;
	template<typename T>
	inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();
		double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.')
		{
			ch=getchar();
			while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
		}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>
	inline void read(T& t,Args&... args){read(t); read(args...);}
	void file()
	{
		#ifndef ONLINE_JUDGE
		freopen("a.txt","r",stdin);
		#endif
	}
	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;
int n,m;
#define Tree sz*40
int root[sz<<1];
int tr[Tree],dep[Tree],ls[Tree],rs[Tree],cnt;
int modify(int &k,int pre,int l,int r,int x,int y)
{
	k=++cnt;ls[k]=ls[pre];rs[k]=rs[pre];
	if (l==r) return (void)(tr[k]=y,dep[k]=dep[pre]),k;
	int mid=(l+r)>>1;
	if (x<=mid) return modify(ls[k],ls[pre],l,mid,x,y);
	return modify(rs[k],rs[pre],mid+1,r,x,y);
}
int query(int k,int l,int r,int x)
{
	if (l==r) return k;
	int mid=(l+r)>>1;
	if (x<=mid) return query(ls[k],l,mid,x);
	return query(rs[k],mid+1,r,x);
}
void build(int &k,int l,int r)
{
	k=++cnt;
	if (l==r) return (void)(tr[k]=l,dep[k]=1);
	int mid=(l+r)>>1;
	build(ls[k],l,mid);build(rs[k],mid+1,r);
}
int cur;
int getfa(int x){int f=query(root[cur],1,n,x);return x==tr[f]?f:getfa(tr[f]);}
void merge(int x,int y)
{
	int xx=getfa(x),yy=getfa(y);
	if (tr[xx]==tr[yy]) return;
	if (dep[xx]>dep[yy]) swap(xx,yy);
	int k=modify(root[cur],root[cur-1],1,n,tr[xx],tr[yy]);
	if (dep[xx]==dep[yy]) ++dep[k];
}
int main()
{
	file();
	int x,y,z;
	read(n,m);
	build(root[0],1,n);
	while (m--)
	{
		read(z);++cur;root[cur]=root[cur-1];
		if (z==1) read(x,y),merge(x,y);
		else if (z==2) read(x),root[cur]=root[x];
		else read(x,y),printf("%d\n",(int)(tr[getfa(x)]==tr[getfa(y)]));
	}
}