#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define vll vector<ll>
#define fr first
#define sc second
#define ins insert
#define sz size()
using namespace std;
const int N = 3e5 + 7;
const int inf = 1e9;
vector<vector<pair<ll,ll>>> g(N);
int p[N];
vll have(N,0);
vll vis(N,0);
ll cen[N];
vector<ll> r;
vector<vll> need(N);
vector<vll> cmp(N);
vll er,er2;
int n;
bool merge(ll a,ll b){
a=p[a],b=p[b];
cen[a]=cen[b];
if(a==b)return false;
if(cmp[a].sz>cmp[b].sz)swap(a,b);
for(auto i : cmp[a]){
cmp[b].pb(i);
p[i]=b;
}
return true;
}
ll bfs(ll v){
queue<ll> q;
q.push(v);
while(q.sz){
ll x=q.front();
q.pop();
if(vis[x])continue;
if(!have[r[x]]){
for(auto i : need[r[x]]){
if(p[x]!=p[i])return p[i];
q.push(i);
}
}
vis[x]=have[r[x]]=1;
er.pb(x);
for(auto i : g[x]){
ll to=i.fr,key=i.sc;
if(have[key]==0){
need[key].pb(to);
er2.pb(key);
}else{
if(p[to]!=p[x])return p[to];
q.push(to);
}
}
}
return -1;
}
void cl(){
for(auto i : er){
have[r[i]]=vis[i]=0;
}
for(auto i : er2) need[i].clear();
er.clear();
er2.clear();
}
vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> c) {
r=R;
n = r.size();
int m=u.size();
for(int i=0;i<m;i++){
g[u[i]].pb({v[i],c[i]});
g[v[i]].pb({u[i],c[i]});
}
vector<int> ans(n,0);
int mn=inf;
set<int> st;
for(int i=0;i<n;i++){
cmp[i].pb(i);
p[i]=i;
cen[i]=i;
}
while(true){
vll to(n,0);
bool f=0;
for(int i=0;i<n;i++){
if(p[i]!=i) continue;
to[i]=bfs(cen[i]);
if(to[i]>=0)f=1;
cl();
}
if(!f)break;
for(int i=0;i<n;i++){
if(p[i]!=i || to[i]==-1) continue;
ll v=p[to[i]];
if(p[i]==v)continue;
merge(i,v);
}
}
for(int i=0;i<n;i++){
if(i!=p[i])continue;
if(p[i]==i)bfs(cen[i]);
for(auto j : er)ans[j]=er.sz;
if(p[i]==i){
mn=min(mn,ans[cen[i]]);
}
cl();
}
for(int i=0;i<n;i++){
if(ans[i]==mn)ans[i]=1;
else ans[i]=0;
}
return ans;
}
