#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
struct node{
    int ls, rs, ans;
}tree[maxn << 6];
int n, m, tot, rtf[maxn], rtd[maxn];

inline int read(){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

int Build(int l, int r){
    int root = ++tot;
    if(l == r) return root;
    int mid = (l + r) >> 1;
    tree[root].ls = Build(l, mid);
    tree[root].rs = Build(mid + 1, r);
    return root;
}

int UpDate(int root, int l, int r, int vis, int pos){
    int c = ++tot;
    tree[c].ls = tree[root].ls;
    tree[c].rs = tree[root].rs;
    if(l == r){
        tree[c].ans = pos;
        return c;
    }
    int mid = (l + r) >> 1;
    if(vis <= mid) tree[c].ls = UpDate(tree[c].ls, l, mid, vis, pos);
    else tree[c].rs = UpDate(tree[c].rs, mid + 1, r, vis, pos);
    return c;
}

int Query(int root, int l, int r, int vis){
    if(l == r) return tree[root].ans;
    int mid = (l + r) >> 1;
    if(vis <= mid) return Query(tree[root].ls, l, mid, vis);
    else return Query(tree[root].rs, mid + 1, r, vis);
}

int gf(int x, int k){
    int ans = Query(rtf[k], 1, n, x);
    return ans == 0 ? x : gf(ans, k);
}

bool judge(int u, int v, int k){
    return gf(u, k) == gf(v, k);
}

void mark(int u, int v, int k){
     u = gf(u, k), v = gf(v, k);
     if(u != v){
        int du = Query(rtd[k], 1, n, u);
        int dv = Query(rtd[k], 1, n, v);
        if(du <= dv){
            rtf[k + 1] = UpDate(rtf[k], 1, n, u, v);
            rtd[k + 1] = UpDate(rtd[k], 1, n, v, max(dv, du + 1));
        }
        else{
            rtf[k + 1] = UpDate(rtf[k], 1, n, v, u);
            rtd[k + 1] = UpDate(rtd[k], 1, n, u, max(du, dv + 1));
        }
     }
     else{
        rtf[k + 1] = rtf[k];
        rtd[k + 1] = rtd[k];
     }
}

int main(){
    int op, u, v, k;
    n = read(), m = read();
    rtf[0] = Build(1, n);
    rtd[0] = Build(1, n);
    for(int i = 1; i <= m; i++){
        op = read();
        if(op == 2){
            k = read();
            rtf[i] = rtf[k];
            rtd[i] = rtd[k];
        }
        else if(op == 1){
            u = read(), v = read();
            mark(u, v, i - 1);
        }
        else{
            u = read(), v = read();
            if(judge(u, v, i - 1)) printf("1\n");
            else printf("0\n");
            rtf[i] = rtf[i - 1];
            rtd[i] = rtd[i - 1];
        }
    }

    return 0;
}