#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e5;
int N, M;
int R[MAXN+10];
int ans[MAXN+10];
set<pii> adj[MAXN+10];
vector<pii> adj2[MAXN+10];
set<int> S[MAXN+10];
int par[MAXN+10];
int vis[MAXN+10];
bool dead[MAXN+10];
struct UF
{
int par[MAXN+10];
int Find(int x)
{
if(x==par[x]) return x;
return par[x]=Find(par[x]);
}
void Union(int x, int y)
{
x=Find(x); y=Find(y);
par[x]=y;
}
void init()
{
for(int i=1; i<=N; i++) par[i]=i;
}
}uf, uf2;
int cnt[MAXN+10];
vector<int> find_reachable(vector<int> _R, vector<int> _U, vector<int> _V, vector<int> _C)
{
N=_R.size(); M=_U.size();
for(int i=1; i<=N; i++) R[i]=_R[i-1]+1;
for(int i=1; i<=M; i++)
{
int u=_U[i-1]+1, v=_V[i-1]+1, w=_C[i-1]+1;
if(R[u]!=w) adj[u].insert({w, v});
else adj2[u].push_back({w, v});
if(R[v]!=w) adj[v].insert({w, u});
else adj2[v].push_back({w, u});
}
uf.init(); uf2.init();
for(int i=1; i<=N; i++)
{
S[i].insert(R[i]);
if(!adj2[i].empty())
{
par[i]=adj2[i].back().second;
uf.Union(i, par[i]);
}
}
queue<int> Q;
for(int i=1; i<=N; i++)
{
int now=i;
while(1)
{
if(vis[now]) break;
vis[now]=i;
if(par[now]==0) break;
now=par[now];
}
if(par[now]!=0 && vis[now]==i) Q.push(now);
}
while(!Q.empty())
{
int now=Q.front(); Q.pop();
now=uf2.Find(now);
vector<int> V;
for(int i=par[now]; i!=now; i=par[i]) V.push_back(i);
for(auto it : V)
{
if(adj[now].size()+adj2[now].size()+S[now].size()<adj[it].size()+adj2[it].size()+S[it].size()) swap(now, it);
for(auto jt : adj2[it]) adj2[now].push_back(jt);
for(auto jt : adj[it])
{
auto pt=S[now].lower_bound(jt.first);
if(pt!=S[now].end() && *pt==jt.first) adj2[now].push_back(jt);
else adj[now].insert(jt);
}
for(auto jt : S[it])
{
for(auto pt=adj[now].lower_bound({jt, 0}); pt!=adj[now].end() && pt->first==jt; pt=adj[now].erase(pt));
S[now].insert(jt);
}
uf2.Union(it, now);
dead[it]=true;
}
while(!adj2[now].empty() && uf2.Find(adj2[now].back().second)==now) adj2[now].pop_back();
if(!adj2[now].empty())
{
par[now]=adj2[now].back().second;
if(uf.Find(now)==uf.Find(par[now])) Q.push(now);
else uf.Union(now, par[now]);
}
else par[now]=0;
}
for(int i=1; i<=N; i++) cnt[uf2.Find(i)]++;
int val=N;
for(int i=1; i<=N; i++) if(!dead[i] && par[i]==0) val=min(val, cnt[uf2.Find(i)]);
for(int i=1; i<=N; i++) if(cnt[uf2.Find(i)]==val) ans[i]=1;
return vector<int>(ans+1, ans+N+1);
}
