蒟蒻比较菜，现在才学。。。
其实就是魔改的主席树啦，记录每个点的直接父亲与这棵子树的大小。
合并的时候不用路径压缩，直接暴力跳父亲，(O(log^2)) 找到祖先，之后启发式合并（启发式合并的平均复杂度达到 (O(log n))）。
需要注意的是可能会先继承删一个版本，并有两次在同一个版本上的修改。这是我们需要先复制版本，再在这个版本上动态开点修改父亲。
$ exttt{code}$
// Author:A weak man named EricQian
#include<bits/stdc++.h>
using namespace std;
#define infll 0x7f7f7f7f7f7f7f7f
#define inf 0x3f3f3f3f
#define Maxn 200005
typedef long long ll;
inline int rd()
{
int x=0;
char ch,t=0;
while(!isdigit(ch = getchar())) t|=ch=='-';
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x=t?-x:x;
}
inline ll maxll(ll x,ll y){ return x>y?x:y; }
inline ll minll(ll x,ll y){ return x<y?x:y; }
inline ll absll(ll x){ return x>0ll?x:-x; }
inline ll gcd(ll x,ll y){ return (y==0)?x:gcd(y,x%y); }
int n,m,tot;
int root[Maxn];
struct TREE { int ls,rs,fa,siz; }tree[Maxn<<5];
void build(int &p,int nl,int nr)
{
if(!p) p=++tot;
if(nl==nr){ tree[p].fa=nl,tree[p].siz=1; return; }
int mid=(nl+nr)>>1;
build(tree[p].ls,nl,mid),build(tree[p].rs,mid+1,nr);
}
TREE query(int p,int nl,int nr,int x)
{
if(nl==nr) return tree[p];
int mid=(nl+nr)>>1;
if(mid>=x) return query(tree[p].ls,nl,mid,x);
else return query(tree[p].rs,mid+1,nr,x);
}
TREE Find(int p,int x)
{
TREE tmp=query(p,1,n,x);
if(tmp.fa==x) return tmp;
return Find(p,tmp.fa);
}
void change(int p,int nl,int nr,int x,int F,int S)
{
if(nl==nr) { tree[p].fa=F,tree[p].siz=S; return; }
int mid=(nl+nr)>>1;
if(mid>=x)
{
tree[++tot]=tree[tree[p].ls],tree[p].ls=tot;
change(tree[p].ls,nl,mid,x,F,S);
}
else
{
tree[++tot]=tree[tree[p].rs],tree[p].rs=tot;
change(tree[p].rs,mid+1,nr,x,F,S);
}
}
int main()
{
//ios::sync_with_stdio(false); cin.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=rd(),m=rd(),build(root[0],1,n);
TREE sa,sb;
for(int i=1,opt,a,b,k;i<=m;i++)
{
opt=rd();
if(opt==1)
{
root[i]=++tot,tree[root[i]]=tree[root[i-1]];
a=rd(),b=rd(),sa=Find(root[i],a),sb=Find(root[i],b);
// if(sa.fa==sb.fa) continue;
if(sa.siz>sb.siz)
change(root[i],1,n,sb.fa,sa.fa,sb.siz),
change(root[i],1,n,sa.fa,sa.fa,sa.siz+sb.siz);
else
change(root[i],1,n,sa.fa,sb.fa,sa.siz),
change(root[i],1,n,sb.fa,sb.fa,sa.siz+sb.siz);
}
else if(opt==2) k=rd(),root[i]=root[k];
else
{
a=rd(),b=rd(),root[i]=root[i-1];
sa=Find(root[i],a),sb=Find(root[i],b);
if(sa.fa==sb.fa) printf("1
");
else printf("0
");
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}