#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 = 2e5 + 7;
const int inf = 1e9;
vector<vector<pair<ll,ll>>> g(N);
int p[N],siz[N];
vll have(N,0);
vll vis(N,0);
ll cen[N];
vector<ll> r;
vector<vll> need(N);
int anc(int a){
return (a == p[a] ? p[a] : p[a] = anc(p[a]));
}
bool uni(int a, int b){
a=anc(a);
b=anc(b);
if(a==b)return false;
if(siz[a]>siz[b])swap(a,b);
siz[b]+=siz[a];
p[a]=b;
return true;
}
bool dfs(ll v){
vis[v]=1;
if(have[r[v]]==0){
have[r[v]]=1;
for(auto i : need[r[v]]){
if(vis[i])continue;
if(uni(v,i)){
cen[anc(v)]=cen[anc(i)];
return true;
}
dfs(i);
}
}
for(auto i : g[v]){
if(vis[i.fr])continue;
if(have[i.sc]==0){
need[i.sc].pb(i.fr);
continue;
}
if(uni(v,i.fr)){
cen[anc(v)]=cen[anc(i.fr)];
return true;
}
if(dfs(i.fr))return true;
}
return false;
}
vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> c) {
r=R;
int 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<ll> st;
for(int i=0;i<n;i++){
st.ins(i);
p[i]=i;
siz[i]=1;
cen[i]=i;
}
while(st.sz){
vll v;
for(auto i : st){
ans[i]=0;
if(p[i]!=i){
v.pb(i);
continue;
}
bool f=dfs(cen[i]);
for(int j=0;j<n;j++){
if(vis[j])ans[i]++;
have[j]=0;
need[j].clear();
}
if(p[i]!=i || !f)v.pb(i);
if(!f) {
for(int j=0;j<n;j++){
if(vis[j])ans[j]=ans[i];
}
mn=min(mn,ans[i]);
}
for(int j=0;j<n;j++){
vis[j]=0;
}
}
for(auto i : v){
st.erase(st.find(i));
}
}
for(int i=0;i<n;i++){
if(mn==ans[i])ans[i]=1;
else ans[i]=0;
}
return ans;
}
