#include <bits/stdc++.h>

#include <ext/rope>

using namespace std;

using namespace __gnu_cxx;
int read() {
    int ans = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) ans = ans * 10 + c - '0', c = getchar();
    return ans * f;
}

struct Node {
    int sz, fa;
    bool operator==(const Node &rhs) const {
        return sz == rhs.sz && fa == rhs.fa;
    }
};

struct Operation {
    int op, x, y, k;
} ops[300005];

rope<Node> *a[300005];

bool used[300005];

int main() {
    int n, m;
    n = read();
    m = read();
    a[0] = new rope<Node>;
    for (int i = 0; i < n; i++) a[0]->push_back({1, i});
    for (int v = 1; v <= m; ++v) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            x = read() - 1;
            y = read() - 1;
            ops[v] = {1, x, y, -1};
        }
        if (op == 2) {
            int k = read();
            ops[v] = {2, -1, -1, k};
            used[k] = true;
        }
        if (op == 3) {
            int x, y;
            x = read() - 1;
            y = read() - 1;
            ops[v] = {3, x, y, -1};
        }
    }
    for (int v = 1; v <= m; ++v) {
        int op = ops[v].op, x = ops[v].x, y = ops[v].y, k = ops[v].k;
        if (op == 1) {
            a[v] = new rope<Node>(*a[v - 1]);
            while (a[v]->at(x).fa != x) x = a[v]->at(x).fa;
            while (a[v]->at(y).fa != y) y = a[v]->at(y).fa;
            if (x == y) continue;
            int sx = a[v]->at(x).sz, sy = a[v]->at(y).sz;
            if (sx < sy) swap(x, y), swap(sx, sy);
            sx += sy;
            Node new_node = {sx, x};
            a[v]->replace(y, &new_node);
        }
        if (op == 2) {
            a[v] = new rope<Node>(*a[k]);
        }
        if (op == 3) {
            a[v] = new rope<Node>(*a[v - 1]);
            while (a[v]->at(x).fa != x) x = a[v]->at(x).fa;
            while (a[v]->at(y).fa != y) y = a[v]->at(y).fa;
            putchar((x == y) + '0');
            putchar('\n');
        }
        if (!used[v - 1]) delete a[v - 1];
    }
}