#include <bits/stdc++.h>
using namespace std;
int n,m,root[100005],cnt=0;
struct node
{
	int tl,tr,deep,fa;
}tree[2000005];
int query(int p,int l,int r,int son)
{
	if(l==r)
		return p;
	int mid=(l+r)/2;
	if(son<=mid)
		return query(tree[p].tl,l,mid,son);
	else
		return query(tree[p].tr,mid+1,r,son);
}
int find(int p,int x)
{
	int id=query(p,1,n,x);
	if(x==tree[id].fa)
		return id;
	else
		return find(p,tree[id].fa);
}
void build(int &p,int l,int r) 
{
    p=++cnt;
    if(l==r)
	{
        tree[p].fa=l;
        tree[p].deep=1;
        return ;
    }
    int mid=(l+r)/2;
    build(tree[p].tl,l,mid);
    build(tree[p].tr,mid+1,r);
    return ;
}
void merge(int last,int &p,int l,int r,int fa,int son)
{
	if(l>son||r<son)
		return ;
	p=++cnt;
	tree[p]=tree[last];
	if(l==r)
	{
		tree[p].fa=fa;
		return ;
	}
	int mid=(l+r)/2;
	if(son<=mid)
		merge(tree[last].tl,tree[p].tl,l,mid,fa,son);
	else
		merge(tree[last].tr,tree[p].tr,mid+1,r,fa,son);
	return ;
}
void dep_add(int p,int l,int r,int add)
{
	if(l==r)
	{
		tree[p].deep++;
		return ;
	}
	int mid=(l+r)/2;
	if(p<=mid)
		dep_add(tree[p].tl,l,mid,add);
	else
		dep_add(tree[p].tr,mid+1,r,add);
	return ;
}
int main()
{
	scanf("%d%d",&n,&m);
	build(root[0],1,n);
	for(int i=1;i<=m;i++)
	{
		int ope,a,b,k;
		scanf("%d",&ope);
		if(ope==1)
		{
			scanf("%d%d",&a,&b);
			root[i]=root[i-1];
			int fa1=find(root[i],a);
			int fa2=find(root[i],b);
			if(tree[fa1].fa!=tree[fa2].fa)
			{
				if(tree[fa1].deep<tree[fa2].deep)
					swap(fa1,fa2);
				merge(root[i-1],root[i],1,n,tree[fa1].fa,tree[fa2].fa);
				if(tree[fa1].deep==tree[fa2].deep)
					dep_add(root[i],1,n,tree[fa1].fa);
			}
		}
		else if(ope==2)
		{
			scanf("%d",&k);
			root[i]=root[k];
		}
		else
		{
			scanf("%d%d",&a,&b);
			root[i]=root[i-1];
			int fa1=find(root[i],a),fa2=find(root[i],b);
			if(tree[fa1].fa==tree[fa2].fa)
				printf("1\n");
			else
				printf("0\n");
		}
	}
	return 0;
}