#include <bits/stdc++.h>
using namespace std;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) ((int) (x).size())
using vi = vector<int>;
using vvi = vector<vi>;
struct edge {
int v, c;
};
struct DSU {
int n; vector<int> par; vector<set<int>> colour;
DSU() {}
DSU(int n, vi &c) : n(n), par(n, -1) {for (int i = 0; i < n; i++) colour[i].insert(c[i]);}
int find(int v) {return par[v] == -1 ? v : par[v] = find(par[v]);}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a != b) {
if (sz(colour[a]) < sz(colour[b])) swap(a, b);
par[b] = a; for (auto &x : colour[b]) colour[a].insert(x);
}
}
};
int timer = 0;
vi seen, tin, cmp;
void dfs(int u, vvi &G, vi &order) {
seen[u] = 1;
for (auto v : G[u]) {
if (seen[v]) continue;
cmp[v] = cmp[u];
dfs(v, G, order);
}
order.push_back(u);
}
vi find_reachable(vi r, vi u, vi v, vi c) {
int n = sz(r), m = sz(u);
vector<vector<edge>> G(n);
// vector<DSU> dsu(n, DSU(n, r));
for (int i = 0; i < m; i++) {
// dsu[c[i]].unite(u[i], v[i]);
G[u[i]].push_back(edge{v[i], c[i]});
G[v[i]].push_back(edge{u[i], c[i]});
}
vi ans(n, 0), p(n, 1); bool found = false;
vvi G2(n), R2(n);
for (int i = 0; i < n; i++) {
bool me = false;
for (auto e : G[i]) {
if (e.c == r[i]) me = true, G2[i].push_back(e.v), R2[e.v].push_back(i);
}
if (!me) found = true, ans[i] = 1;
}
if (found) return ans;
seen.assign(n, 0); cmp.assign(n, -1); vi order1, order2;
for (int i = 0; i < n; i++) if (!seen[i]) cmp[i] = timer++, dfs(i, G2, order1);
reverse(all(order1));
seen.assign(n, 0); cmp.assign(n, -1); timer = 0;
for (auto i : order1) if (!seen[i]) cmp[i] = timer++, dfs(i, R2, order2);
int CMPS = timer;
vector<set<int>> avail(CMPS);
for (int i = 0; i < n; i++) {
avail[cmp[i]].insert(r[i]);
}
vi exists(CMPS, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (cmp[u[j]] == cmp[v[j]]) continue;
int ca = cmp[u[j]], cb = cmp[v[j]];
int req = c[j];
if (avail[ca].count(req) && avail[cb].count(req)) {
for (int k = 0; k < n; k++) if (cmp[k] == cb) cmp[k] = ca;
for (auto &x : avail[cb]) avail[ca].insert(x);
exists[cb] = 0;
}
}
}
vvi G3(CMPS); vi deg(CMPS), csz(CMPS);
for (int i = 0; i < m; i++) {
int ca = cmp[u[i]], cb = cmp[v[i]];
int req = c[i];
if (ca == cb) continue;
if (avail[ca].count(req)) G3[ca].push_back(cb), deg[cb]++;
else if (avail[cb].count(req)) G3[cb].push_back(ca), deg[ca]++;
}
for (int i = 0; i < n; i++) csz[cmp[i]]++;
vi order, st;
for (int i = 0; i < CMPS; i++) if (exists[i] && deg[i] == 0) st.push_back(i);
while (!st.empty()) {
int i = st.back(); st.pop_back();
order.push_back(i);
for (auto v : G3[i]) {
if (--deg[v] == 0) st.push_back(v);
}
}
reverse(order.begin(), order.end());
vi dp(CMPS);
for (auto i : order) {
dp[i] = csz[i];
for (auto v : G3[i]) dp[i] += dp[v];
}
int mn = n; for (int i = 0; i < CMPS; i++) if (exists[i]) mn = min(mn, dp[i]);
for (int i = 0; i < n; i++) ans[i] = dp[cmp[i]] == mn;
return ans;
}
