#include<bits/stdc++.h>
using namespace std;
struct point{int l,r,son[2],num;};
struct chairmantree{
	public: int root[100010],vtot,len;point node[200010*18];
	private:
		bool inset(int n,int now){return(n >= node[now].l&&n <= node[now].r);}
		void setup(int now,int L,int R,bool start){
			node[now].l = L,node[now].r = R;
			if(L == R){
				if(start)node[now].num = L;
				else node[now].num = 1;
				return;
			}
			int mid = (L+R)/2;
			node[now].son[0] = ++len;setup(node[now].son[0],L,mid,start);
			node[now].son[1] = ++len;setup(node[now].son[1],mid+1,R,start);
		}
		void update(int addr,int newval,int now,int from){
			int L = node[from].l,R = node[from].r;
			node[now].l = L;
			node[now].r = R;
			if(L == R&&R == addr){node[now].num = newval;return;}
			if(inset(addr,node[from].son[0])){
				node[now].son[1] = node[from].son[1];
				node[now].son[0] = ++len;
				update(addr,newval,node[now].son[0],node[from].son[0]);
			}else{
				node[now].son[0] = node[from].son[0];
				node[now].son[1] = ++len;
				update(addr,newval,node[now].son[1],node[from].son[1]);
			}
		}
		int findnum(int addr,int now){
			if(node[now].l == node[now].r&&node[now].r == addr){return node[now].num;}
			if(inset(addr,node[now].son[0])){return findnum(addr,node[now].son[0]);}
			else{return findnum(addr,node[now].son[1]);}
		}
	public:
		void setup(int N,bool start){
			root[0] = ++len;
			setup(root[0],1,N,start);
		}
		void update(int addr,int newval,int from){
			root[++vtot] = ++len;
			update(addr,newval,root[vtot],root[from]);
		}
		int findans(int addr,int v){return findnum(addr,root[v]);}
};
struct Unionfind{
	chairmantree fa,si;int nowv;
	void back(int v){
		fa.root[++fa.vtot] = ++fa.len;
		fa.node[fa.len] = fa.node[fa.root[v]];
		si.root[++si.vtot] = ++si.len;
		si.node[si.len] = si.node[si.root[v]];
		nowv++;
	}
	int ancestor(int now){
		int F = fa.findans(now,nowv);
		if(F == now)return now;
		else return ancestor(F);
	}
	bool equalancestor(int a,int b){
		a = ancestor(a);b = ancestor(b);
		return a == b;
	}
	void mix(int a,int b){
		a = ancestor(a);b = ancestor(b);
		if(si.findans(a,nowv) > si.findans(b,nowv)) swap(a,b);
		fa.update(a,b,nowv);
		int SA = si.findans(a,nowv),SB = si.findans(b,nowv);
		si.update(b,SA+SB,nowv);
		++nowv;
	}
	void start(int len){
		nowv = 0;
		fa.setup(len,1);
		si.setup(len,0);
	}
}U;
int N,Q;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> N >> Q;
	U.start(N);
	while(Q--){
		int x,y,op;cin >> op;
		if(op == 1){
			cin >> x >> y;
			U.mix(x,y);
		}
		else if(op == 2){
			cin >> x;
			U.back(x);
		}else{
			cin >> x >> y;
			cout << U.equalancestor(x,y) <<"\n";
			U.back(U.nowv);
		}
	}
	return 0;
}