#pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include "bits/stdc++.h" #define MAXN 100009 #define INF 1000000007 #define mp(x,y) make_pair(x,y) #define all(v) v.begin(),v.end() #define pb(x) push_back(x) #define wr cout<<"----------------"<<endl; #define ppb() pop_back() #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++) #define ff first #define ss second #define my_little_dodge 46 #define debug(x) cerr<< #x <<" = "<< x<<endl; using namespace std; typedef long long ll; typedef pair<int,int> PII; template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} const int buffer=1<<13; char buff[buffer]; int cnt=0; int getInt() { int number = 0; while(buff[cnt] < '0' || '9' < buff[cnt]) if(++cnt >= buffer) fread(buff, buffer, 1, stdin), cnt = 0; while('0' <= buff[cnt] && buff[cnt] <= '9') { number = number * 10 + buff[cnt] - '0'; if(++cnt >= buffer) fread(buff, buffer, 1, stdin), cnt = 0; } return number; } PII arr[MAXN]; int ata[MAXN],vis[MAXN],ans[MAXN],tim,sz[MAXN]; stack<pair<PII,PII> >old; int tap(int x){ if(ata[x]==x) return x; return tap(ata[x]); } void merge(int x,int y){ if((x=tap(x))==(y=tap(y))) return; if(sz[x]<sz[y]) swap(x,y); tim++; old.push(mp(mp(y,tim),mp(x,sz[y]))); sz[x]+=sz[y]; ata[y]=x; } vector<PII>s[MAXN<<2]; void upd(int l,int r,PII v,int nd,int x,int y){ if(l>y or x>r) return; if(l<=x and y<=r){ s[nd].pb(v); return; } int mid=(x+y)>>1; upd(l,r,v,nd<<1,x,mid); upd(l,r,v,nd<<1|1,mid+1,y); } void recover(int x){ while(!old.empty() and old.top().ff.ss>x){ pair<PII,PII> nd=old.top();old.pop(); sz[nd.ss.ff]-=nd.ss.ss; ata[nd.ff.ff]=nd.ff.ff; } } void solve(int nd,int x,int y){ int wagt=tim; tr(it,s[nd]) merge(it->ff,it->ss); if(x==y){ if(vis[x]){ if(tap(arr[x].ff)==tap(arr[x].ss)) ans[x]=1; else ans[x]=0; } return; } int mid=(x+y)>>1; solve(nd<<1,x,mid); solve(nd<<1|1,mid+1,y); recover(wagt); } int main(){ //~ freopen("file.in", "r", stdin); int n,q; scanf("%d%d",&n,&q); stack<int>st; for(int i=1;i<=n;i++) ata[i]=i,sz[i]=1; for(int i=1;i<=q;i++){ int t=getInt(); if(t==1){ int x=getInt(),y=getInt(); st.push(i); arr[i]=mp(x,y); } else if(t==2){ int x=getInt(); while(x-- and !st.empty()){ int nd=st.top();st.pop(); upd(nd,i-1,arr[nd],1,1,q); } } else{ int x=getInt(),y=getInt(); vis[i]=1; arr[i]=mp(x,y); } } while(!st.empty()){ int nd=st.top();st.pop(); upd(nd,q,arr[nd],1,1,q); } solve(1,1,q); for(int i=1;i<=q;i++) if(vis[i]) printf("%d\n",ans[i]); return 0; }