思路：
主席树维护可持久化数组
剩下的就是普通的并查集了…
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200050;
int n,m,op,xx,yy,L[N*50],R[N*50],tree[N*50],root[N],cnt;
void build(int l,int r,int &pos){
if(!pos)pos=++cnt;
if(l==r){tree[pos]=l;return;}
int mid=(l+r)>>1;
build(l,mid,L[pos]),build(mid+1,r,R[pos]);
}
int query(int l,int r,int pos,int x){
if(l==r)return tree[pos];
int mid=(l+r)>>1;
if(mid<x)return query(mid+1,r,R[pos],x);
else return query(l,mid,L[pos],x);
}
void insert(int last,int l,int r,int &pos,int x,int change){
pos=++cnt;
if(l==r){tree[pos]=change;return;}
int mid=(l+r)>>1;
if(mid<x)L[pos]=L[last],insert(R[last],mid+1,r,R[pos],x,change);
else R[pos]=R[last],insert(L[last],l,mid,L[pos],x,change);
}
int find(int &root,int x){
int temp=query(1,n,root,x);
if(x==temp)return x;
int res=find(root,temp);
insert(root,1,n,root,x,res);
return res;
}
int main(){
scanf("%d%d",&n,&m),build(1,n,root[0]);
for(int i=1;i<=m;i++){
scanf("%d",&op);
if(op==1){
scanf("%d%d",&xx,&yy);
int fx=find(root[i-1],xx),fy=find(root[i-1],yy);
insert(root[i-1],1,n,root[i],fx,fy);
}
else if(op==2)scanf("%d",&xx),root[i]=root[xx];
else{
root[i]=root[i-1],scanf("%d%d",&xx,&yy);
if(find(root[i],xx)!=find(root[i],yy))puts("0");
else puts("1");
}
}
}