#include <cstring>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cmath>

using namespace std;

const int N=20005;

bool isd(char ch){

	return '0'<=ch&&ch<='9';

}

void read(int &x){

	x=0;

	char ch=getchar();

	while (!isd(ch))

		ch=getchar();

	while (isd(ch))

		x=x*10+ch-48,ch=getchar();

}

int n,m,size,root[N],fa[N*50],ls[N*50],rs[N*50],depth[N*50];

int build(int L,int R){

	int rt=++size;

	if (L==R){

		fa[rt]=L,depth[rt]=0;

		return rt;

	}

	int mid=(L+R)>>1;

	ls[rt]=build(L,mid);

	rs[rt]=build(mid+1,R);

	return rt;

}

int query(int rt,int le,int ri,int pos){

	if (le==ri)

		return rt;

	int mid=(le+ri)>>1;

	if (pos<=mid)

		return query(ls[rt],le,mid,pos);

	else

		return query(rs[rt],mid+1,ri,pos);

}

void Modify(int prt,int &rt,int le,int ri,int pos,int val){

	rt=++size;

	if (le==ri){

		fa[rt]=val;

		depth[rt]=depth[prt];

		return;

	}

	ls[rt]=ls[prt],rs[rt]=rs[prt];

	int mid=(le+ri)>>1;

	if (pos<=mid)

		Modify(ls[prt],ls[rt],le,mid,pos,val);

	else

		Modify(rs[prt],rs[rt],mid+1,ri,pos,val);

}

void add(int rt,int le,int ri,int pos){

	if (le==ri){

		depth[rt]++;

		return;

	}

	int mid=(le+ri)>>1;

	if (pos<=mid)

		add(ls[rt],le,mid,pos);

	else

		add(rs[rt],mid+1,ri,pos);

}

int find(int rt,int pos){

	int p=query(rt,1,n,pos);

	if (pos==fa[p])

		return p;

	return find(rt,fa[p]);

}

int main(){

	size=0;

	read(n),read(m);

	root[0]=build(1,n);

	for (int i=1;i<=m;i++){

		int op,a,b;

		root[i]=root[i-1];

		read(op),read(a);

		if (op==1){

			read(b);

			a=find(root[i],a),b=find(root[i],b);

			if (fa[a]==fa[b])

				continue;

			if (depth[a]>depth[b])

				swap(a,b);

			Modify(root[i-1],root[i],1,n,fa[a],fa[b]);

			if (depth[a]==depth[b])

				add(root[i],1,n,fa[b]);

		}

		else if (op==2)

			root[i]=root[a];

		else {

			root[i]=root[i-1];

			read(b);

			a=find(root[i],a),b=find(root[i],b);

			printf("%d\n",fa[a]==fa[b]);

		}

	}

	return 0;

}