#include <vector>
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
int search(int n, int s, vi &r, vector<vector<ii>> &L) {
vi viz(n, 0);
set<int> ToVisit, Chei;
ToVisit.insert(s);
vector<vi> Locked(n); /// daca as avea cheia i, le-as putea vizita
Chei.insert(r[s]);
viz[s] = 1;
while(!ToVisit.empty()) {
auto u = *ToVisit.begin();
ToVisit.erase(u);
int c = r[u];
if(!Chei.count(c)) {
Chei.insert(c);
for(auto it2 : Locked[c]) {
if(!viz[it2]) {
ToVisit.insert(it2);
viz[it2] = 1;
}
}
Locked[c].clear();
}
for(auto [it, cul] : L[u]) {
if(viz[it]) continue;
if(Chei.count(cul)) {
viz[it] = 1;
ToVisit.insert(it);
} else {
Locked[cul].push_back(it);
}
}
}
int re = 0;
for(auto it : viz) re += it;
return re;
}
vi find_reachable(vi r, vi u, vi v, vi c) {
int n = r.size(), m = u.size();
vector<vector<ii>> L(n);
for(int i = 0; i < m; ++i) {
L[u[i]].push_back({v[i], c[i]});
L[v[i]].push_back({u[i], c[i]});
}
vi ans(n, 0), re(n, 0);
for(int i = 0; i < n; ++i)
ans[i] = search(n, i, r, L);
int mi = ans[0];
for(auto it : ans) mi = min(mi, it);
for(int i = 0; i < n; ++i)
re[i] = (ans[i] == mi);
return re;
}
