/**************************************************************

     Problem: 3673

     User: idy002

     Language: C++

     Result: Accepted

     Time:76 ms

     Memory:13780 kb

 ****************************************************************/

 #include <cstdio>

 #include <algorithm>

 #define N 20010

 using namespace std;

 struct Node {

     int u, p, s;

     Node *ls, *rs;

 }pool[N*], *tail=pool, *root[N];

 int n, m;

 Node *build( int lf, int rg ) {

     Node *nd = ++tail;

     if( lf==rg ) {

         nd->u = lf;

         nd->p = lf;

         nd->s = ;

         return nd;

     }

     int mid=(lf+rg)>>;

     nd->ls = build( lf, mid );

     nd->rs = build( mid+, rg );

     return nd;

 }

 Node *modify( Node *nd, int lf, int rg, int u, int p, int s ) {

     Node *nn = ++tail;

     if( lf==rg ) {

         nn->u = u;

         nn->p = p;

         nn->s = s;

         return nn;

     }

     int mid=(lf+rg)>>;

     if( u<=mid ) {

         nn->ls = modify( nd->ls, lf, mid, u, p, s );

         nn->rs = nd->rs;

     } else {

         nn->ls = nd->ls;

         nn->rs = modify( nd->rs, mid+, rg, u, p, s );

     }

     return nn;

 }

 Node *query( Node *nd, int lf, int rg, int u ) {

     if( lf==rg ) return nd;

     int mid=(lf+rg)>>;

     if( u<=mid ) return query(nd->ls,lf,mid,u);

     else return query(nd->rs,mid+,rg,u);

 }

 Node *find( Node *r, int a ) {

     Node *na = query(r,,n,a);

     while( na->u!=na->p ) na=query(r,,n,na->p);

     return na;

 }

 int main() {

     scanf( "%d%d", &n, &m );

     root[] = build(,n);

     for( int i=,opt,a,b,k; i<=m; i++ ) {

         scanf( "%d", &opt );

         if( opt== ) {

             scanf( "%d%d", &a, &b );

             root[i] = root[i-];

             Node *na = find(root[i],a);

             Node *nb = find(root[i],b);

             if( na==nb ) continue;

             if( na->s > nb->s ) swap(na,nb);

             root[i] = modify( root[i], , n, na->u, nb->u, na->s );

             root[i] = modify( root[i], , n, nb->u, nb->u, na->s+nb->s );

         } else if( opt== ) {

             scanf( "%d", &k );

             root[i] = root[k];

         } else {

             scanf( "%d%d", &a, &b );

             root[i] = root[i-];

             printf( "%d\n", find(root[i],a)->u==find(root[i],b)->u );

         }

     }

 }