#include <iostream>
using namespace std;
const int N = 2e5 + 10; 
int n, m;
struct segment
{
	struct seg { int v, ls, rs; } s[N << 6];
	int a[N], rt[N], tot;
	void build(int l, int r, int&u)
	{
		if (u == 0) u = ++tot;
		int mid = (l + r) / 2;
		if (l == r) s[u].v = a[l];
		else build(l, mid, s[u].ls), build(mid + 1, r, s[u].rs);
	}
	int query(int L, int R, int p, int u)
	{
		if (L == R) return s[u].v;
		int mid = (L + R) / 2;
		if (p <= mid) return query(L, mid, p, s[u].ls);
		else return query(mid + 1, R, p, s[u].rs);
	}
	void update(int l, int r, int p, int x, int lst, int&u)
	{
		if (u == 0) u = ++tot;
		if (l == r) { s[u].v = x; return ; }
		int mid = (l + r) / 2;
		if (p <= mid) s[u].ls = ++tot, s[u].rs = s[lst].rs, s[s[u].ls] = s[s[lst].ls], update(l, mid, p, x, s[lst].ls, s[u].ls);
		else s[u].ls = s[lst].ls, s[u].rs = ++tot, s[s[u].rs] = s[s[lst].rs], update(mid + 1, r, p, x, s[lst].rs, s[u].rs);
	}
} fa, dep; 
int find(int x, int u)
{
	if (x == fa.query(1, n, x, u)) return x;
	return find(fa.query(1, n, x, u), u);
}
void join(int x, int y, int id, int lst)
{
	int f1 = find(x, fa.rt[lst]), f2 = find(y, fa.rt[lst]), d1 = dep.query(1, n, f1, dep.rt[lst]), d2 = dep.query(1, n, f2, dep.rt[lst]);
	if (f1 == f2) return ;
	if (d1 >= d2) fa.update(1, n, f2, f1, fa.rt[lst], fa.rt[id]), dep.update(1, n, f1, max(d1, d2 + 1), dep.rt[lst], dep.rt[id]);
	else fa.update(1, n, f1, f2, fa.rt[lst], fa.rt[id]), dep.rt[id] = dep.rt[lst];
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) fa.a[i] = i, dep.a[i] = 1;
	fa.build(1, n, fa.rt[0]); dep.build(1, n, dep.rt[0]);
	for (int i = 1; i <= m; i++)
	{
		int op, x, y;
		cin >> op;
		if (op == 1)
		{
			cin >> x >> y;
			join(x, y, i, i - 1);
		}
		else if (op == 2) 
		{
		    cin >> x;
		    fa.rt[i] = fa.rt[x]; dep.rt[i] = dep.rt[x];
		}
		else
		{
		    fa.rt[i] = fa.rt[i - 1]; dep.rt[i] = dep.rt[i - 1];
			cin >> x >> y;
			cout << (find(x, fa.rt[i]) == find(y, fa.rt[i])) << endl;
		}
	}
	return 0;
}