#include <cstdio>
#include <iostream>
#define mid (l + r >> 1)
#define sz(_) (_ == nullptr ? 0 : _->siz)
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
struct node {
    node *lp, *rp;
    int val, pa, siz;
    node (int val) {
        lp = rp = nullptr;
        this->val = pa = val, siz = 1;
    }
    node (node *p) {
        lp = p->lp, rp = p->rp;
        val = p->val, pa = p->pa, siz = p->siz;
    }
} *root[maxn];
node *build(int l, int r) {
    if (l == r) return new node(l);
    node *p = new node(0);
    p->lp = build(l, mid), p->rp = build(mid + 1, r);
    return p;
}
//在p中pos的地址
node *find_id(node *p, int l, int r, int pos) {
    while (l < r) {
        if (pos <= mid) p = p->lp, r = mid;
        else p = p->rp, l = mid + 1;
    }
    return p;
}
//在u中pos的祖先的地址
node *find_fa(node *u, int pos) {
    node *p = find_id(u, 1, n, pos);
    while (p->pa != p->val) {
        p = find_id(u, 1, n, p->pa);
    }
    return p;
}
//在u的基础上对pos1,pos2两个即将修改的位置建新树,并返回根节点地址
node *get_new(node *u, int pos1, int pos2) {
    node *rt = new node(u), *p = rt;
    int l = 1, r = n, pos = pos1;
    while (l < r) {
        if (pos <= mid) {
            p->lp = new node(p->lp);
            p = p->lp, r = mid;
        } else {
            p->rp = new node(p->rp);
            p = p->rp, l = mid + 1;
        }
    }
    p = rt;
    l = 1, r = n, pos = pos2;
    bool tag = true;
    while (l < r) {
        tag &= (l <= pos1 && pos1 <= r);//当pos1在[l, r]中时,不用建新的节点
        if (pos <= mid) {
            if (!tag) p->lp = new node(p->lp);
            p = p->lp, r = mid;
        } else {
            if (!tag) p->rp = new node(p->rp);
            p = p->rp, l = mid + 1;
        }
    }
    return rt;
}
//按秩合并,返回根节点地址
node *merge(node *u, int x, int y) {
    node *fx = find_fa(u, x), *fy = find_fa(u, y);
    if (fx == fy) return u;
    if (sz(fx) < sz(fy)) swap(fx, fy), swap(x, y);
    node *p = get_new(u, fx->val, fy->val);
    fx = find_id(p, 1, n, fx->val), fy = find_id(p, 1, n, fy->val);
    fx->pa = fy->val, fy->siz += fx->siz;
    return p;
}
int main() {
    scanf("%d%d", &n, &m);
    root[0] = build(1, n);
    for (int i = 1, op, a, b, k = 0; i <= m; i++) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d", &a, &b);
            root[i] = merge(root[k], a, b);
            k = i;
        } else if (op == 2) {
            scanf("%d", &k);
            root[i] = root[k];
        } else {
            scanf("%d%d", &a, &b);
            root[i] = root[k];
            node *fx = find_fa(root[i], a), *fy = find_fa(root[i], b);
            if (fx == fy) printf("1\n");
            else printf("0\n");
        }
    }
    return 0;
}