#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
struct node
{
	int lc, rc, fa, siz;	
}ST[N << 6];
int root[N], tot, num, n, m;
inline int clone(int ind)
{
	ST[++tot] = ST[ind];
	return tot;
}
inline int build(int ind, int l, int r)
{
	ind = ++tot;
	if(l == r)
	{
		ST[ind].fa = l;
		ST[ind].siz = 1;
		return ind;
	}
	int mid = (l + r) >> 1;
	ST[ind].lc = build(ST[ind].lc, l, mid);
	ST[ind].rc = build(ST[ind].rc, mid + 1, r);
	return ind;
}
inline int upd(int ind, int l, int r, int tl, int tr, int x, int y)
{
	ind = clone(ind);
	if(tl <= l && r <= tr)
	{
		ST[ind].fa = x;
		ST[ind].siz = y;
		return ind;
	}
	int mid = (l + r) >> 1;
	if(tl <= mid)
		ST[ind].lc = upd(ST[ind].lc, l, mid, tl, tr, x, y);
	if(tr > mid)
		ST[ind].rc = upd(ST[ind].rc, mid + 1, r, tl, tr, x, y);
	return ind;
}
inline pair<int, int> ask(int ind, int l, int r, int tl, int tr)
{
	if(tl <= l && r <= tr)
		return make_pair(ST[ind].fa, ST[ind].siz);
	int mid = (l + r) >> 1;
	if(tl <= mid)
		return ask(ST[ind].lc, l, mid, tl, tr);
	return ask(ST[ind].rc, mid + 1, r, tl, tr);
}
inline pair<int, int> find(int x)
{
	pair<int, int>ed = ask(root[num], 1, n, x, x);
	if(ed.first == x)
		return ed;
	return find(ed.first);
}
inline void merge(int u, int v)
{
	pair<int, int> r1 = find(u), r2 = find(v);
	if(r1.first == r2.first)
	{
		root[++num] = root[num-1];
		return;
	}
	if(r1.second < r2.second)
	{
		/*
		r1根树接到r2根树下
		f[r1] = r2 
		*/
		root[++num] = upd(root[num-1], 1, n, 
		r1.first, r1.first, r2.first, r1.second + r2.second); 
	}
	else
	{
		/*
		r2根树接到r1根树下
		f[r2] = r1 
		*/
		root[++num] = upd(root[num-1], 1, n, 
		r2.first, r2.first, r1.first, r1.second + r2.second);
	}
}
inline bool connected(int u, int v)
{
	return find(u).first == find(v).first;
}
int main()
{
	cin >> n >> m;
	root[0] = build(1, 1, n);
	int op, a, b, k;
	while(m--)
	{
		scanf("%d", &op);
		if(op == 1)
		{
			scanf("%d%d", &a, &b);
			merge(a, b);
		}
		else if(op == 2)
		{
			scanf("%d", &k);
			root[++num] = root[k];
		}
		else
		{
			scanf("%d%d", &a, &b);
			cout << connected(a, b) << "\n";
			root[++num] = root[num-1];
		}
	}
	return 0; 
}