代码，64pts

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mid_A ((l+r)>>1)
#define Debug cerr<<"Passed line #"<<__LINE__<<" in function ["<<__FUNCTION__<<"].\n"
inline int qread(){
    char c=getchar();register int num=0,f=1;
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) num=num*10+c-'0';
    return num*f;
}
namespace mutable_dsu{
	class dsu{
		#define MAXN_B 100010
		public:
		int root[MAXN_B<<5];
		private:
		struct node{
			int lson,rson,fa,dep;
			node(int v){
				fa=v,dep=1;
				lson=rson=0;
			}
			node(node &b){
				lson=b.lson,rson=b.rson;
			}
			node(){
			}
		};
		node tree[MAXN_B<<5];
		int cnt=0,n;
		int build(int l,int r){
			cnt++;
			register int now=cnt;
			if(l==r){tree[now]=node(l);return now;}	
			tree[now].lson=build(l,mid_A);
			tree[now].rson=build(mid_A+1,r);
			return now;
		}
		int merge(int last,int l,int r,int pos,int val){
			cnt++;
			register int now=cnt;
			tree[now]=node(tree[last]);
			if(l==r){
				tree[now].fa=val;
				tree[now].dep=tree[last].dep;
				return now;
			}
			if(pos<=mid_A)tree[now].lson=merge(tree[last].lson,l,mid_A,pos,val);
			else tree[now].rson=merge(tree[last].rson,mid_A+1,r,pos,val);
			return now;
		}
		void update(int now,int l,int r,int pos){
			if(l==r){tree[now].dep++;return;}
			if(pos<=mid_A)update(tree[now].lson,l,mid_A,pos);
			else update(tree[now].rson,mid_A+1,r,pos);
		}
		int query(int now,int l,int r,int pos){
			if(l==r)return now;
			if(pos<=mid_A)return query(tree[now].lson,l,mid_A,pos);
			else return query(tree[now].rson,mid_A+1,r,pos);
		}
		int find(int rt,int x){
			register int now=query(rt,1,n,x);
			if(x==tree[now].fa){return now;}
			return find(rt,tree[now].fa);
		}
		public:
		inline void init(int n){
			this->n=n;
			root[0]=build(1,n);
		}
		inline void merge(int edition,int a,int b){
			root[edition]=root[edition-1];
			register int faa=find(root[edition],a),fab=find(root[edition],b);
			if(tree[faa].fa!=tree[fab].fa){
				if(tree[faa].dep>tree[fab].dep)swap(faa,fab);
				root[edition]=merge(root[edition-1],1,n,tree[faa].fa,tree[fab].fa);
				if(tree[faa].dep==tree[fab].dep)update(root[edition],1,n,tree[fab].fa);
			}
		}
		inline bool samepath(int edition,int a,int b){
			root[edition]=root[edition-1];
			return find(root[edition],a)==find(root[edition],b);
		}
		#undef MAXN_B
	};
} 
using namespace mutable_dsu;
dsu tree;
signed main(){
	register int n,m;
	n=qread();m=qread();
	srand(time(NULL));
	tree.init(n);
	for(register int i=1;i<=m;i++){
		register int op,x,y;
		op=qread();x=qread();
		if(op==1){
			y=qread();
			tree.merge(i,x,y);
		}else if(op==2){
			tree.root[i]=tree.root[x];
		}else{
			y=qread();
			printf("%d\n",tree.samepath(i,x,y));
		}
	}
}