#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int ls[N<<5],rs[N<<5],fa[N<<5],dep[N<<5],rt[N<<1];
int cnt,n,m;
void build(int l,int r,int &p){
    p=++cnt;if(l==r){fa[p]=l;return;}
    int mid=l+r>>1;
    build(l,mid,ls[p]);
    build(mid+1,r,rs[p]);
}
void merge(int x,int k,int l,int r,int pre,int &p){
    p=++cnt;ls[p]=ls[pre];rs[p]=rs[pre];
    if(l==r){fa[p]=k;dep[p]=dep[pre];return;}
    int mid=l+r>>1;
    if(x<=mid)merge(x,k,l,mid,ls[pre],ls[p]);
    else merge(x,k,mid+1,r,rs[pre],rs[p]);
}
void update(int x,int l,int r,int p){
    if(l==r){++dep[p];return;}
    int mid=l+r>>1;
    update(x,l,mid,ls[p]);
    update(x,mid+1,r,rs[p]);
}
int query(int x,int l,int r,int p){
    if(l==r)return p;
    int mid=l+r>>1;
    if(x<=mid)return query(x,l,mid,ls[p]);
    else return query(x,mid+1,r,rs[p]);
}
int find(int x,int rt){
    int at=query(x,1,n,rt);
    // printf("%d\n",x);
    return fa[at]^x?find(fa[at],rt):at;
}
int main(){
    // freopen("P3402.in","r",stdin);
    // freopen("P3402.out","w",stdout);
    ios::sync_with_stdio(cin.tie(cout.tie(0)));
    cin>>n>>m;build(1,n,rt[0]);
    for(int i=1,op,x,y;i<=m;++i){
        cin>>op;
        if(op==1){
            cin>>x>>y;rt[i]=rt[i-1];
            x=find(x,rt[i]);y=find(y,rt[i]);
            if(fa[x]==fa[y])continue;
            if(dep[x]>dep[y])swap(x,y);
            merge(fa[x],fa[y],1,n,rt[i-1],rt[i]);
            if(dep[x]==dep[y])update(fa[y],1,n,rt[i]);
        }else if(op==2)cin>>x,rt[i]=rt[x];
        else if(op==3){
            cin>>x>>y;rt[i]=rt[i-1];
            x=find(x,rt[i]);y=find(y,rt[i]);
            printf("%d\n",fa[x]==fa[y]);
        }
    }
    return 0;
}