rt，我启发式合并由于假了 T 了第2和5点，随机化调参一直不过第十四点，最后根据编号大小交换过了（？

#include <iostream>
#include <random>
#include <ctime>
#define Kamisato namespace
#define Ayaka std;
using Kamisato Ayaka

char buf[1<<20],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline int read(){ int x=0;
	char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return x;
}
const int N=2e5+5;
int n,m,tot,rt[N<<2],f[N<<5];
struct node{ int l,r; }t[N<<5];
inline void build(int &x,int l,int r){ x=++tot;
	if(l==r) return f[x]=l,void(); int mid=l+r>>1;
	build(t[x].l,l,mid),build(t[x].r,mid+1,r);
}
int upd(int x,int l,int r,int p,int k){
	int y=++tot; t[y]=t[x]; if(l==r) return f[y]=k,y; int mid=l+r>>1;
	p<=mid?t[y].l=upd(t[x].l,l,mid,p,k):t[y].r=upd(t[x].r,mid+1,r,p,k); return y;
}
inline int ask(int x,int l,int r,int p){
	if(l==r) return x; int mid=l+r>>1;
	return p<=mid?ask(t[x].l,l,mid,p):ask(t[x].r,mid+1,r,p);
}
inline int find(int v,int x){ int fa=ask(rt[v],1,n,x); return x==f[fa]?fa:find(v,f[fa]); }
int main(){
	n=read(),m=read();
	build(rt[0],1,n);
	for(int i=1;i<=m;i++){
		int op,x,y; rt[i]=rt[i-1];
		op=read(),x=read();
		if(op==1){ y=read();
			if(x>y) swap(x,y);
			x=find(i,x),y=find(i,y);
			if(x^y) rt[i]=upd(rt[i],1,n,f[y],f[x]);
		}else if(op==2) rt[i]=rt[x];
		else if(op==3) y=read(),printf("%d\n",find(i,x)==find(i,y));
	} return 0;
}