思路：按树深度合并，把 $fa,dep$ 可持久化。

症状：查找父节点时结果均为 $0$，所以输出的答案均为 $1$。

//程序算法：可持久化并查集
//下面的namespace IO 在IDE里面可以折叠起来不用看
#include <bits/stdc++.h>

namespace IO{
    void file() {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }

    #define gc getchar
    #define pc putchar

    template <typename T>
    inline void read(T &x) {
        x = 0;
        bool f = 0;
        T s = 1;
        char ch = gc();
        while (!isdigit(ch) && ~ch) {
            f = (ch == '-');
            ch = gc();
        }

        while (isdigit(ch)) {
            x = x * 10 + (ch - 48);
            ch = gc();
        }

        if (ch == '.') {
            ch = gc();
            while (isdigit(ch)) {
                s *= 0.1;
                x += (ch - 48) * s;
                ch = gc();
            }
        }
        if (f) x = -x;
    }

    template <typename T>
    inline void write(T x) {
        if (x < 0) {
            pc('-');
            x = -x;
        }

        if (x >= 10) write(x / 10);
        pc(x % 10 + 48);
    }

    using std::string;
    inline void read(string &s) {
        s.clear();
        char ch = gc();
        while (isspace(ch)) ch = gc();
        while (!isspace(ch) && ~ch) s += ch, ch = gc();
    }

    inline void read(char &ch) {
        ch = gc();
        while (isspace(ch)) ch = gc();
    }

    inline void write(const string s) {
        for (auto ch : s) pc(ch);
    }

    inline void write(const char ch) {
        pc(ch);
    }

    inline void write(const double x) {
        printf("%.3Lf", (long double)x);
    }

    inline void write(const char *s) {
        while (*s) pc(*(s++));
    }

    template <typename T, typename ...t>
    inline void read(T &x, t &...y) {
        read(x);
        read(y...);
    }

    template <typename T, typename ...t>
    inline void write(T x, t ...y) {
        write(x);
        write(y...);
    }
}

using namespace IO;
using namespace std;
const int N = 1e5 + 10;

int ls[N << 7], rs[N << 7], fa[N << 7], dep[N << 7], root[N];
int n, m, tot;

int modify_fa(int rt, int l, int r, int x, int v) {
    int k = ++tot;
    ls[k] = ls[rt], rs[k] = rs[rt];
    if (l == r) {
        fa[k] = v, dep[k] = dep[rt];
        return k;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) ls[k] = modify_fa(ls[k], l, mid, x, v);
    else rs[k] = modify_fa(rs[k], mid + 1, r, x, v);

    return k;
}

int modify_dep(int rt, int l, int r, int x, int v) {
    int k = ++tot;
    ls[k] = ls[rt], rs[k] = rs[rt];
    if (l == r) {
        dep[k] = dep[rt] + v;
        fa[k] = fa[rt];
        return k;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) ls[k] = modify_dep(ls[k], l, mid, x, v);
    else rs[k] = modify_dep(rs[k], mid + 1, r, x, v);

    return k;
}

int query_fa(int rt, int l, int r, int x) {
    if (l == r) return fa[rt];
    int mid = (l + r) >> 1;
    if (x <= mid) return query_fa(ls[rt], l, mid, x);
    return query_fa(rs[rt], mid + 1, r, x);
}

int query_dep(int rt, int l, int r, int x) {
    if (l == r) return dep[rt];
    int mid = (l + r) >> 1;
    if (x <= mid) return query_dep(ls[rt], l, mid, x);
    return query_dep(rs[rt], mid + 1, r, x);
}

int find(int rt, int u) {
    int f = query_fa(rt, 1, n, u);
    if (f == u) return f;
    return find(rt, f);
}

void merge(int rt, int u, int v) {
    u = find(root[rt - 1], u), v = find(root[rt - 1], v);
    if (u == v) {
        root[rt] = root[rt - 1];
        return;
    }

    int du = query_dep(root[rt - 1], 1, n, u);
    int dv = query_dep(root[rt - 1], 1, n, v);
    if (du < dv) swap(u, v);
    root[rt] = modify_fa(root[rt - 1], 1, n, v, u);
    if (du == dv) root[rt] = modify_dep(root[rt], 1, n, u, 1);
}

int main() {
    read(n, m);
    for (int i = 1; i <= n; i++) {
        root[0] = modify_fa(root[0], 1, n, i, i);
        // root[0] = modify_dep(root[0], 1, n, i, 1);
    }
    
    for (int x = 1; x <= m; x++) {
        int op;
        read(op);
        if (op == 1) {
            int a, b;
            read(a, b);
            merge(root[x], a, b);
        }
        else if (op == 2) {
            int k;
            read(k);
            root[x] = root[k];
        }
        else {
            int a, b;
            read(a, b);
            root[x] = root[x - 1];
            a = find(root[x], a), b = find(root[x], b);
            // write(a, ' ', b);
            // puts("");
            if (a == b) puts("1");
            else puts("0");
        }
    }
    return 0;
}