#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> _u, std::vector<int> _v, std::vector<int> _c) {
int N = r.size();
int M = _u.size();
vector<vector<array<int, 2>>> adj(N);
for (int i = 0; i < M; ++i) {
adj[_u[i]].push_back({_v[i], _c[i]});
adj[_v[i]].push_back({_u[i], _c[i]});
}
vector<int> color(N);
vector<int> scc(N);
for (int i = 0; i < N; ++i) {
color[i] |= (1 << r[i]);
}
vector<int> ret(N);
for (int _ = 0; _ < 30; ++_) {
int timer = 0;
scc = vector<int>(N, 0);
vector<int> state(N), tot(N + 1), out;
auto dfs = [&](auto& dfs, int v) -> void {
state[v] = 1;
for (auto& [u, c] : adj[v]) {
if (state[u] != 1 && (color[v] & (1 << c)) > 0) {
dfs(dfs, u);
}
}
out.push_back(v);
};
for (int i = 0; i < N; ++i) {
if (state[i] == 0) {
dfs(dfs, i);
}
}
reverse(begin(out), end(out));
auto rdfs = [&](auto& rdfs, int v) -> void {
state[v] = 2;
scc[v] = timer;
tot[scc[v]] |= color[v];
for (auto& [u, c] : adj[v]) {
if (state[u] != 2 && (color[u] & (1 << c)) > 0) {
rdfs(rdfs, u);
}
}
};
for (int it = 0; it < (int)out.size(); ++it) {
int i = out[it];
// cout << i << " -> ";
if (state[i] != 2) {
timer += 1;
rdfs(rdfs, i);
}
}
// cout << "\n";
for (int i = 0; i < N; ++i) {
color[i] = tot[scc[i]];
}
vector<int> valid(timer + 1, 1), sz(N);
for (int i = 0; i < N; ++i) {
for (auto& [u, c] : adj[i]) {
if (((1 << c) & color[i]) > 0 && scc[i] != scc[u]) {
valid[scc[i]] = 0; // sz[i] >= sz[i] + sz[scc[i]] > sz[scc[i]] => sz[i] != min(sz), i.e. we can go from scc[i] -> scc[u]
}
}
sz[scc[i]] += 1;
}
// for (int i = 0; i < N; ++i) {
// cout << scc[i] << " ";
// }
// cout << "\n";
if (_ + 1 < 30) continue;
int res = INT_MAX;
for (int i = 1; i <= timer; ++i) {
if (valid[i]) {
res = min(res, sz[i]);
}
}
// for (int i = 0; i < N; ++i) {
// cout << scc[i] << " ";
// }
// cout << "\n";
for (int i = 0; i < N; ++i) {
ret[i] = (res == sz[scc[i]] && valid[scc[i]]);
}
}
return ret;
}
