#include<bits/stdc++.h>
using namespace std;
int fa[100010],siz[100010]; 
int op[200010],p[200010],q[200010],ans[200010];
vector<int>edge[200010]; stack<int>st;
int find(int p){
	return fa[p]==p?p:fa[p]=find(fa[p]);
} 
void merge(int p,int q){
	int p1=find(p),p2=find(q);
	if(p1==p2) return ; // 两点已经属于同一集合 
	if(siz[p1]<siz[p2]) swap(p1,p2);
	fa[p2]=p1; siz[p1]+=siz[p2]; st.push(p2);
}
void dfs(int id){ int cnt=st.size();
	if(op[id]==1) merge(p[id],q[id]);
	if(op[id]==3) ans[id]=find(p[id])==find(q[id]); 
	for(auto p:edge[id]) dfs(p); // 搜索 id 的儿子 
	while(st.size()>cnt){ //撤回所有操作 
		int p=st.top(); st.pop(); // 取出栈顶元素 
		siz[fa[p]]-=siz[p]; fa[p]=p; // 让点 p 独立 
	}
}  
int main(){
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&op[i],&p[i]);
		if(op[i]==2) edge[p[i]].push_back(i);
		else scanf("%d",&q[i]),edge[i-1].push_back(i);
	} dfs(0); // 可持久化并查集离线维护，深搜 
	for(int i=1;i<=m;i++){
		if(op[i]==3) printf("%d\n",ans[i]); // 输出答案 
	} return 0; // robot robot robot
}

https://www.luogu.com.cn/record/114474867