代码：

#include <bits/stdc++.h>
#define IOS1 std::ios::sync_with_stdio(false)
#define IOS2 std::cin.tie(nullptr)

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

inline void write(int x)
{
	if (x < 0)
		putchar('-'), x = -x;
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
	return;
}

static constexpr int N = 2e5;

int n, mark, vsMark;
int fa[N << 5], dep[N << 5], ls[N << 5], rs[N << 5], rt[N];

inline int build(int l, int r)
{
	int ind = ++mark;
	if (r - l == 1)
	{
		fa[ind] = l;
		dep[ind] = 1;
		return ind;
	}
	int mid = l + r >> 1;
	ls[ind] = build(l, mid);
	rs[ind] = build(mid, r);
	return ind;
}

inline void DSU()/* : n(init_.size()), mark(-1), vsMark(-1) */
{
	mark = -1;
	vsMark = -1;
	// fa.resize((N << 5) + 10);
	// dep.resize((N << 5) + 10);
	// rt.resize(N + 10);
	// ls.resize((N << 5) + 10);
	// rs.resize((N << 5) + 10);
	rt[++vsMark] = build(0, n);
}

inline int query(int p, int l, int r, int x, int y)
{
	if (l >= y || r <= x)
	{
		return 0;
	}
	if (l >= x && r <= y)
	{
		return p;
	}
	int mid = (l + r) / 2;
	return query(ls[p], l, mid, x, y) + query(rs[p], mid, r, x, y);
}

inline int query(int vs, int x, int y)
{
	return query(rt[vs], 0, n, x, y);
}

inline int modify(int p, int l, int r, int x, int v)
{
	int ind = ++mark;
	if (r - l == 1)
	{
		fa[ind] = v;
		return ind;
	}
	int mid = l + r >> 1;
	if (x < mid) ls[ind] = modify(ls[p], l, mid, x, v), rs[ind] = rs[p];
	else rs[ind] = modify(rs[p], mid, r, x, v), ls[ind] = ls[p];
	return ind;
}

inline void modify(int vs, int x, int v)
{
	rt[++vsMark] = modify(rt[vs], 0, n, x, v);
}

inline int find(int vs, int x)
{
	int p = query(vs, x, x + 1);
	if (fa[p] == x) return p;
	else return find(vs, fa[p]);
}

inline int findVal(int vs, int x)
{
	return fa[find(vs, x)];
}

inline void emptyOp()
{
	rt[++vsMark] = rt[vsMark];
}

inline void copyKth(int k)
{
	rt[++vsMark] = rt[k];
}

inline void merge(int vs, int x, int y)
{
	int p1 = find(vs, x), p2 = find(vs, y);
	if (fa[p1] != fa[p2])
	{
		if (dep[p1] == dep[p2])
		{
			modify(vs, fa[p1], fa[p2]);
			++dep[p2];
		}
		else if (dep[p1] < dep[p2])
		{
			modify(vs, fa[p1], fa[p2]);
		}
		else
		{
			modify(vs, fa[p2], fa[p1]);
		}
	}
	else
	{
		emptyOp();
	}
}

int main()
{
	IOS1;
	IOS2;

    n = read();
    int q = read();
    // std::cin >> n >> q;
    // DSU seg(a);
    DSU();
    while (q--)
    {
        int op = read();
        // std::cin >> op;
        if (op == 1)
        {
            int a = read(), b = read();
            --a, --b;
            // std::cin >> a >> b;
            // seg.merge(seg.vsMark, a, b);
            merge(vsMark, a, b);
        }
        else if (op == 2)
        {
            int k = read();
            // std::cin >> k;
            // seg.modify(k, 0, seg.fa[seg.query(k, 0, 1)]);
            copyKth(k);
        }
        else
        {
            int a = read(), b = read();
            --a, --b;
            // std::cin >> a >> b;
            // int k = seg.vsMark;
            // int val1 = seg.findVal(k, a), val2 = seg.findVal(k, b);
            int val1 = findVal(vsMark, a), val2 = findVal(vsMark, b);
            // std::cout << (val1 == val2) << "\n";
            write(val1 == val2);
            printf("\n");
            // seg.emptyOp();
            emptyOp();
        }
    }

	return 0;
}