n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0

0<n,m<=2*10^4

101

#include<cstdio>#include<ext/rope>#include<iostream>using namespace std;using namespace __gnu_cxx;inline int Rin(){  int x=0,c=getchar(),f=1;  for(;c<48||c>57;c=getchar())    if(!(c^45))f=-1;  for(;c>47&&c<58;c=getchar())    x=(x<<1)+(x<<3)+c-48;  return x*f;}const int M=20010;rope<int>*his[M];int n,m,a[M];inline int find(int i,int x){  int d=x,p;  while(his[i]->at(x)^x)x=his[i]->at(x);  while(d^x)p=his[i]->at(d),his[i]->replace(d,x),d=p;  return x;}inline void merge(int i,int x,int y){  x=find(i,x),y=find(i,y);  if(x^y)    his[i]->replace(y,x);}int main(){  n=Rin(),m=Rin();  for(int i=1;i<=n;i++)a[i]=i;  his[0]=new rope<int>(a,a+1+n);  for(int i=1,x,y,sign;i<=m;i++){    his[i]=new rope<int>(*his[i-1]);    scanf("%d",&sign);    switch(sign){    case 1:      x=Rin(),y=Rin();      merge(i,x,y);      break;    case 2:      x=Rin();      his[i]=his[x];      break;    case 3:      x=Rin(),y=Rin();      printf("%d\n",(!(find(i,x)^find(i,y))));      break;    }  }  return 0;}