#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
const int N = 1e5 + 9,M = 2e5 + 9;
int n,m,ans;
int id;
struct Segment_tree{
	struct node{
	    int fa,siz;
		int lchild,rchild;
	} t[M << 6];
	int Root[M],cnt;
	void build(int &new_root,int l,int r){
		cnt++;
	    new_root = cnt;
	    if(l == r){
			t[new_root].fa = l;
			t[new_root].siz = 1;
			return;
		}
	    build(t[new_root].lchild,l,mid);
		build(t[new_root].rchild,mid + 1,r);
	}
	int query_fa(int root,int l,int r,int k){
	    if(l == r)
	        return t[root].fa;
	    if(k <= mid)
			return query_fa(t[root].lchild,l,mid,k);
		else
			return query_fa(t[root].rchild,mid + 1,r,k);
	}
	int query_siz(int root,int l,int r,int k){
	    if(l == r)
	        return t[root].siz;
	    if(k <= mid)
			return query_fa(t[root].lchild,l,mid,k);
		else
			return query_fa(t[root].rchild,mid + 1,r,k);
	}
	void update_fa(int root,int &new_root,int l,int r,int k,int v){
		if(!new_root){
			cnt++;
			new_root = cnt;
		}
		if(l == r){
			t[new_root].fa = v;
			return;
		}
		if(k <= mid){
			t[new_root].rchild = t[root].rchild;
			t[new_root].lchild = ++cnt;
			t[t[new_root].lchild] = t[t[root].lchild];
			update_fa(t[root].lchild,t[new_root].lchild,l,mid,k,v);
		}
		else{
			t[new_root].lchild = t[root].lchild;
			t[new_root].rchild = ++cnt;
			t[t[new_root].rchild] = t[t[root].rchild];
			update_fa(t[root].rchild,t[new_root].rchild,mid + 1,r,k,v);
		}
	}
	void update_siz(int root,int &new_root,int l,int r,int k,int v){
		if(!new_root){
			cnt++;
			new_root = cnt;
		}
		if(l == r){
			t[new_root].siz = t[root].siz + v;
			return;
		}
		if(k <= mid){
			t[new_root].rchild = t[root].rchild;
			t[new_root].lchild = ++cnt;
			t[t[new_root].lchild] = t[t[root].lchild];
			update_fa(t[root].lchild,t[new_root].lchild,l,mid,k,v);
		}
		else{
			t[new_root].lchild = t[root].lchild;
			t[new_root].rchild = ++cnt;
			t[t[new_root].rchild] = t[t[root].rchild];
			update_fa(t[root].rchild,t[new_root].rchild,mid + 1,r,k,v);
		}
	}
}seg;
int father(int x){
	int get = seg.query_fa(seg.Root[id - 1],1,n,x);
	if(get == x)
		return x;
	return father(get);
}
void merge(int x,int y){
	int fa_x = father(x),fa_y = father(y);
	int siz_x = seg.query_siz(seg.Root[id - 1],1,n,fa_x);
	int siz_y = seg.query_siz(seg.Root[id - 1],1,n,fa_y);
	if(siz_x > siz_y){
		seg.update_fa(seg.Root[id - 1],seg.Root[id],1,n,fa_y,fa_x);
		seg.update_siz(seg.Root[id - 1],seg.Root[id],1,n,fa_x,siz_y);
	}
	else{
		seg.update_fa(seg.Root[id - 1],seg.Root[id],1,n,fa_x,fa_y);
		seg.update_siz(seg.Root[id - 1],seg.Root[id],1,n,fa_y,siz_x);
	}
}
int check(int x,int y){
	int fa_x = father(x),fa_y = father(y);
	//cout << x << ' ' << y << ' ' << fa_x << ' ' << fa_y << '\n';
	return fa_x == fa_y;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin >> n >> m;
    seg.build(seg.Root[0],1,n);
    //cout << "build successfully\n";
    for(id = 1;id <= m;id++){
    	//cout << '\n';
        int op,a,b,k;
        cin >> op;
        if(op == 2){
        	cin >> k;
        	//k ^= ans;
            seg.Root[id] = seg.Root[k];
        	//cout << op << ' ' << k << '\n';
		}
		else{
			cin >> a >> b;
			//a ^= ans;b ^= ans;
			//cout << op << ' ' << a << ' ' << b << '\n';
		}
		if(op == 1)
			merge(a,b);
		else if(op == 3){
			ans = check(a,b);
			cout << ans << '\n';
			//cout << '\n';
		}
    }
    return 0;
}