#include <bits/stdc++.h>
#define ll int
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN=3e5+1;
vector<pair<ll,ll>>grafo[MAXN];
ll ke[MAXN], cant[MAXN], vis[MAXN], tim=1, comp, id[MAXN];
unordered_set<ll>comps[MAXN];
unordered_map<ll,vector<ll>>esp;
unordered_set<ll>keys;
bool dfs(ll nod)
{
comps[comp].insert(nod);
if(cant[nod]!=0)
{
auto it=comps[id[nod]].find(comp);
if(it!=comps[id[nod]].end())
id[comp]=id[nod];
return 1;
}
vis[nod]=tim;
cant[comp]++;
keys.insert(ke[nod]);
for(auto k:esp[ke[nod]])
{
if(vis[k]!=tim)
{
if(dfs(k))
return 1;
}
}
esp[ke[nod]].resize(0);
for(auto k:grafo[nod])
{
auto it=keys.find(k.se);
if(vis[k.fr]!=tim&&it!=keys.end())
{
if(dfs(k.fr))
return 1;
}
else if(it==keys.end())
{
esp[k.se].pb(k.fr);
}
}
return 0;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
ll i, mi=INT_MAX;
for(i=0; i<sz(u); i++)
{
grafo[u[i]].pb({v[i],c[i]});
grafo[v[i]].pb({u[i],c[i]});
}
for(i=0; i<sz(r); i++)
{
ke[i]=r[i];
id[i]=i;
}
vector<ll>rec(sz(r));
for(i=0; i<sz(r); i++)
rec[sz(r)-i-1]=i;
for(i=0; i<sz(r); i++)
{
comp=rec[i];
tim++;
keys.clear();
esp.clear();
if(dfs(rec[i]))
{
if(id[rec[i]]==rec[i])
cant[rec[i]]=MAXN;
else
cant[rec[i]]=cant[id[rec[i]]];
}
}
for(i=0; i<sz(r); i++)
{
mi=min(mi,cant[i]);
}
vector<int>ans(sz(r),0);
for(i=0; i<sz(r); i++)
{
if(cant[i]==mi)
ans[i]=1;
}
return ans;
}
