#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll dfs(ll node,vector<ll> &vis,vector<vector<ll>> &adj){
if(vis[node]) return 0;
vis[node]=1;
int am = 1;
for(auto el:adj[node]){
if(!vis[el]){
//vis[el]=1;
am += dfs(el,vis,adj);
}
}
return am;
}
ll dfs2(int node,vector<int> r, vector<int> u, vector<int> v, vector<int> c,vector<vector<pair<ll,ll>>> adj){
stack<int> st;
set<pair<ll,ll>> paths;
map<ll,ll> keys;
map<ll,ll> visitedNodes;
keys[r[node]] = 1;
st.push(node);
int ans = 0;
while(!st.empty()){
ll nnode = st.top();
st.pop();
if(visitedNodes[nnode]) continue;
keys[r[nnode]]=1;
ans++;
visitedNodes[nnode]=1;
for(auto el:adj[nnode]){
if(visitedNodes[el.first]) continue;
if(!visitedNodes[el.first] && keys[el.second]>0){
st.push(el.first);
}else{
paths.insert({el.first,el.second});
}
}
set<pair<ll,ll>> npaths;
for(auto el:paths){
if(visitedNodes[el.first]) continue;
if(keys[el.second]){
st.push(el.first);
}else{
npaths.insert({el.first,el.second});
}
}
paths = npaths;
}
return ans;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
vector<int> ans(r.size(), 0);
int n = r.size();
int m = v.size();
vector<vector<pair<ll,ll>>> adj(n+2);
for(ll i=0;i<m;i++){
adj[v[i]].push_back({u[i],c[i]});
adj[u[i]].push_back({v[i],c[i]});
}
int mini = 1e9;
int type = c[0];
// for(int i=0;i<n;i++){
// if(r[i]==type) {
// vector<ll> vis(n+2);
// ans[i] = dfs(i,vis,adj);
// }else{
// ans[i] = 1;
// }
// mini = min(mini,ans[i]);
// }
for(int i=0;i<n;i++){
ans[i] = dfs2(i,r,u,v,c,adj);
mini = min(ans[i],mini);
}
for(int i=0;i<n;i++) ans[i] = ans[i]==mini ? 1 : 0;
return ans;
}
