传送门
//minamoto
#include<bits/stdc++.h>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int read(){
int res,f=1;char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
const int N=2e5+5;
int n,m,fa[N<<5],dep[N<<5],L[N<<5],R[N<<5],rt[N],cnt;
void build(int &p,int l,int r){
p=++cnt;if(l==r)return (void)(fa[p]=l);
int mid=(l+r)>>1;
build(L[p],l,mid),build(R[p],mid+1,r);
}
void upd(int &p,int las,int l,int r,int x,int v){
p=++cnt;if(l==r)return (void)(fa[p]=v,dep[p]=dep[las]);
L[p]=L[las],R[p]=R[las];int mid=(l+r)>>1;
x<=mid?upd(L[p],L[las],l,mid,x,v):upd(R[p],R[las],mid+1,r,x,v);
}
int query(int p,int l,int r,int x){
if(l==r)return p;int mid=(l+r)>>1;
return x<=mid?query(L[p],l,mid,x):query(R[p],mid+1,r,x);
}
void add(int p,int l,int r,int x){
if(l==r)return (void)(++dep[p]);
int mid=(l+r)>>1;
x<=mid?add(L[p],l,mid,x):add(R[p],mid+1,r,x);
}
int find(int id,int x){
int fat=query(id,1,n,x);
return x==fa[fat]?fat:find(id,fa[fat]);
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),m=read(),build(rt[0],1,n);
for(int i=1;i<=m;++i){
int op=read();
switch(op){
case 1:{
int x=read(),y=read();rt[i]=rt[i-1];
int fatx=find(rt[i],x),faty=find(rt[i],y);
if(fatx==faty)continue;if(dep[fatx]>dep[faty])swap(fatx,faty);
upd(rt[i],rt[i-1],1,n,fa[fatx],fa[faty]);
if(dep[fatx]==dep[faty])add(rt[i],1,n,fa[faty]);
break;
}
case 2:{
int k=read();rt[i]=rt[k];
break;
}
case 3:{
int x=read(),y=read();rt[i]=rt[i-1];
int fatx=find(rt[i],x),faty=find(rt[i],y);
puts(fatx==faty?"1":"0");
break;
}
}
}
return 0;
}