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

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

#include<cstdio>

#include<ext/rope>

#include<iostream>

using namespace std;

using namespace __gnu_cxx;

inline int Rin(){

  int x=,c=getchar(),f=;

  for(;c<||c>;c=getchar())

    if(!(c^))f=-;

  for(;c>&&c<;c=getchar())

    x=(x<<)+(x<<)+c-;

  return x*f;

}

const int M=;

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=;i<=n;i++)a[i]=i;

  his[]=new rope<int>(a,a++n);

  for(int i=,x,y,sign;i<=m;i++){

    his[i]=new rope<int>(*his[i-]);

    scanf("%d",&sign);

    switch(sign){

    case :

      x=Rin(),y=Rin();

      merge(i,x,y);

      break;

    case :

      x=Rin();

      his[i]=his[x];

      break;

    case :

      x=Rin(),y=Rin();

      printf("%d\n",(!(find(i,x)^find(i,y))));

      break;

    }

  }

  return ;

}