#include<iostream>
using namespace std;
struct tr{
	int ls,rs,fa,h;
}tr[20000008];
int N,M;
int root[2000008],idx=1,now;
void init(int p,int l,int r)
{
	if(l==r)
	{
		tr[p]={0,0,l,1};
		return ;
	}
	tr[p].ls=++idx;tr[p].rs=++idx; 
	init(tr[p].ls,l,(l+r)>>1);
	init(tr[p].rs,((l+r)>>1)+1,r);
}
void modify(int &p,int l,int r,int gox,int fa)
{
	++idx;
	tr[idx]=tr[p];
	p=idx;
	if(l==r)
	{
		tr[p].fa=fa;
		return ;
	}
	if(tr[p].ls&&gox<=((l+r)>>1)) modify(tr[p].ls,l,(l+r)>>1,gox,fa);
	else if(tr[p].rs&&gox>((l+r)>>1)) modify(tr[p].rs,((l+r)>>1)+1,r,gox,fa);
}
int query(int p,int l,int r,int gox)
{
	if(l==r) return p;
	if(gox<=((l+r)>>1)) return query(tr[p].ls,l,(l+r)>>1,gox);
	else return query(tr[p].rs,((l+r)>>1)+1,r,gox);
}
int findfa(int x)
{
	int fx=query(now,1,N,x);
	if(tr[fx].fa==x) return fx;
	return findfa(tr[fx].fa);
}
void hebing(int x,int y,int id)
{
	int fx=findfa(x),fy=findfa(y);
	if(tr[fx].fa==tr[fy].fa) return ;
	if(tr[fx].h>tr[fy].h) swap(fx,fy);
	if(tr[fx].h==tr[fy].h) tr[fy].h++;
	modify(now,1,N,tr[fx].fa,tr[fy].fa);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i,j,k,opt,u,v;
	cin>>N>>M;
	init(1,1,N);
	root[0]=1;now=1;
	for(i=1;i<=M;i++)
	{
		cin>>opt;
		if(opt==3)
		{
			cin>>u>>v;
			if(findfa(u)==findfa(v)) cout<<"1\n";
			else cout<<"0\n";
		}
		else if(opt==1)
		{
			cin>>u>>v;
			hebing(u,v,i);
		}
		else
		{
			cin>>u;
			now=root[u];
		}
		root[i]=now;
	}
	return 0;
}
/*
2 2
1 1 2
3 1 2
*/