#include<bits/stdc++.h>
using namespace std;
const int maxn = (1e5 + 10) * (50);

int n, m;

int t[maxn], ls[maxn], rs[maxn], ht[maxn], rep;

void cop(int x1, int x2){ t[x1] = t[x2], ls[x1] = ls[x2], rs[x1] = rs[x2], ht[x1] = ht[x2];}

#define mid ((l+r) >> 1)
#define pii pair<int, int>

int rt[maxn];

pii qry(int x, int l, int r, int dir){
	if(l == r) return {t[x], ht[x]};
	if(dir <= mid) return qry(ls[x], l, mid, dir);
	else return qry(rs[x], mid+1, r, dir);
}

void chg(int &x, int l, int r, int dir, int cg_f, int cg_ht){
	cop(rep+1, x), x = ++rep;
	if(l == r) return ht[x] = cg_ht, t[x] = cg_f, void();
	if(dir <= mid) chg(ls[x], l, mid, dir, cg_f, cg_ht);
	else chg(rs[x], mid+1, r, dir, cg_f, cg_ht);
}

pii gt_ast(int x, int ver){
	pii nd = qry(rt[ver], 1, n ,x);
	while(x != nd.first){
		x = nd.first;
		nd = qry(rt[ver], 1, n, x);
	}
	return nd;
}
pii a, b;
void uni(int x, int y, int ver){
	a = gt_ast(x, ver); b = gt_ast(y, ver);
	if(a.first == b.first) return;
	if(a.second < b.second) {
		chg(rt[ver], 1, n, a.first, b.first, max(a.second+1, b.second));
	}else{
		chg(rt[ver], 1, n, b.first, a.first, max(a.second, b.second+1));
	}
}

bool insame(int x, int y, int ver){
	pii a, b;
	a = gt_ast(x, ver); b = gt_ast(y, ver);
	if(a.first == b.first) return 1;
	else return 0;
}

void tst(int x, int l, int r){
	if(l == r) return printf("%d [%d] f:%d\n", x, l, t[x]), void();
	tst(ls[x], l, mid); tst(rs[x], mid+1, r);
}

signed main(){
	cin >> n >> m; 
	int pre_rt = 0;
	for (int i = 1; i <= n; i++) chg(pre_rt, 1, n, i, i, 1);
	rt[0] = pre_rt;
	
	for (int i = 1, opt, a, b, k; i <= m; i++){
		rt[i] = rt[i-1];
		scanf("%d", &opt);
		if(opt == 1){
			scanf("%d%d", &a, &b);
			uni(a, b, i);
		}else if(opt == 2){
			scanf("%d", &k);
			rt[i] = rt[k];
		}else{
			scanf("%d%d", &a, &b);
			cout << insame(a, b, i) << "\n";
		}
	}
	return 0;
}