#include<bits/stdc++.h>
using namespace std;
const int N=100005;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct tree {
	int l,r,fa,dep;
} t[N*50];
int n,m,rt[N*10],cnt;
void build(int &p,int l,int r) {
	p=++cnt;
	if(l==r){
		t[p].fa=l;
		return;
	}
	int mid=(l+r)>>1;
	build(t[p].l,l,mid);
	build(t[p].r,mid+1,r);
}
void change(int &p,int last,int l,int r,int pos,int ff) {
	p=++cnt;
	if(l==r){
		t[p].fa=ff;
		t[p].dep=t[last].dep;
		return;
	}
	t[p].l=t[last].l,t[p].r=t[last].r;
	int mid=(l+r)>>1;
	if(pos<=mid)change(t[p].l,t[last].l,l,mid,pos,ff);
	else change(t[p].r,t[last].r,mid+1,r,pos,ff);
	return;
}
int query(int p,int l,int r,int pos) {
	if(l==r)return p;
	int mid=(l+r)>>1;
	if(pos<=mid)return query(t[p].l,l,mid,pos);
	else return query(t[p].r,mid+1,r,pos);
}
int root(int v,int x){
	int k=query(v,1,n,x);
	if(x==t[k].fa)return k;
	return root(v,t[k].fa);
}
void add(int p,int l,int r,int pos){
	if(l==r){
		++t[p].dep;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)add(t[pos].l,l,mid,pos);
	else add(t[pos].r,mid+1,r,pos);
}
int main() {
	n=read(),m=read();
	build(rt[0],1,n);
	for(int i=1; i<=m; i++) {
		int opt,a,b;
		opt=read();
		if(opt==1){
			rt[i]=rt[i-1];
			a=read(),b=read();
			a=root(rt[i],a);
			b=root(rt[i],b);
			if(t[a].fa==t[b].fa)continue;
			if(t[a].dep>t[b].dep)swap(a,b);
			change(rt[i],rt[i-1],1,n,t[a].fa,t[b].fa);
			if(t[a].dep==t[b].dep)add(rt[i],1,n,t[b].fa);
		}
		if(opt==2){
			a=read();
			rt[i]=rt[a];
		}
		if(opt==3){
			rt[i]=rt[i-1];
			a=read(),b=read();
			a=root(rt[i],a);
			b=root(rt[i],b);
			if(t[a].fa==t[b].fa)puts("1");
			else puts("0");
		}
	}
	return 0;
}