RT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=6e6+5;
int n,m;
struct p_sgm_t{
	int fa[MAXN],sz[MAXN],ls[MAXN],rs[MAXN],tot,rt[MAXN];
	void init(){
		memset(fa,0,sizeof(fa));
		memset(sz,0,sizeof(sz));
		memset(fa,0,sizeof(ls));
		memset(sz,0,sizeof(rs));
		memset(fa,0,sizeof(rt));
		tot=0;
		return;
	}
	void build(int &id,int L,int R){
		if(L>R)return;
		id=++tot;
		if(L==R){
			fa[id]=L;
			sz[id]=1;
			return;
		}
		int mid=(L+R)>>1;
		build(ls[id],L,mid);
		build(rs[id],mid+1,R);
		return;
	}
	void modify(int id,int &new_id,int L,int R,int k,int father,int delta){
		if(L>R)return;
		new_id=++tot;
		fa[new_id]=fa[id],sz[new_id]=sz[id];
		if(L==R){
			fa[id]=father;
			sz[id]+=delta;
			return;
		}
		ls[new_id]=ls[id],rs[new_id]=rs[id];
		int mid=(L+R)>>1;
		if(k<=mid)modify(ls[id],ls[new_id],L,mid,k,father,delta);
		else modify(rs[id],rs[new_id],mid+1,R,k,father,delta);
		return;
	}
	int query_fa(int id,int L,int R,int k){
		if(L>R||k<L||k>R)return 0;
		if(L==R)return fa[id];
		int mid=(L+R)>>1;
		if(k<=mid)return query_fa(ls[id],L,mid,k);
		else return query_fa(rs[id],mid+1,R,k);
	}
	int query_sz(int id,int L,int R,int k){
		if(L>R||k<L||k>R)return 0;
		if(L==R)return sz[id];
		int mid=(L+R)>>1;
		if(k<=mid)return query_sz(ls[id],L,mid,k);
		else return query_sz(rs[id],mid+1,R,k);
	}
}FA,SZ;
int ver; 
int op,x,y,f_x,f_y,sz_x,sz_y;
int find(ll qwq){
//	cout<<ver<<" <"<<endl;
	int qwq_fa=FA.query_fa(FA.rt[ver],1,n,qwq);
	cout<<qwq_fa<<"fff"<<endl;
	if(qwq==qwq_fa)return qwq_fa;
	return find(qwq_fa);
}
int main(){
	cin>>n>>m;
	FA.init();
	FA.build(FA.rt[0],1,n);
	SZ.init();
	SZ.build(SZ.rt[0],1,n);
	for(int i=1;i<=m;i++){
		cin>>op;
		if(op==1){
			cin>>x>>y;
			f_x=find(x),f_y=find(y);
			sz_x=SZ.query_sz(SZ.rt[ver],1,n,f_x),sz_y=SZ.query_sz(SZ.rt[ver],1,n,f_y);
			cout<<f_x<<" "<<f_y<<" "<<sz_x<<" "<<sz_y<<endl; 
			if(sz_x>sz_y)swap(f_x,f_y),swap(sz_x,sz_y);
			cout<<ver<<endl;
			FA.modify(FA.rt[ver],FA.rt[i],1,n,f_x,f_y,0);
			SZ.modify(SZ.rt[ver],SZ.rt[i],1,n,f_y,f_y,sz_x);
			ver=i;
		}
		else if(op==2)cin>>ver;
		else{
			cin>>x>>y;
			f_x=find(x),f_y=find(y);
			cout<<f_x<<" -- "<<f_y<<endl;
			cout<<(f_x==f_y)<<'\n';
		}
	}
	return 0;
}

样例过不去！