#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, siz; vector<set<int>> colour;
DSU() {}
DSU(int n, vi &c) : n(n), par(n, -1), siz(n, 1), colour(n) {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 (siz[a] < siz[b]) swap(a, b);
if (sz(colour[a]) < sz(colour[b])) swap(colour[a], colour[b]);
par[b] = a; for (auto &x : colour[b]) colour[a].insert(x);
siz[a] += siz[b];
}
}
};
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);
set<int> cc;
// 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]});
cc.insert(c[i]);
}
vi ans(n, 0), p(n, 1); bool found = false;
vvi G2(n), R2(n);
for (int i = 0; i < n; i++) {
cc.insert(r[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;
auto dsu = DSU(n, r);
vi head(CMPS, -1);
vector<set<int>> avail(CMPS);
for (int i = 0; i < n; i++) {
// avail[cmp[i]].insert(r[i]);
if (head[cmp[i]] == -1) head[cmp[i]] = i;
else dsu.unite(head[cmp[i]], i);
}
vvi G3(CMPS); vi deg(CMPS), csz(CMPS), exists(CMPS, 1);
for (int i = 0; i < n; i++) csz[cmp[i]]++;
// literally just this part is slow
bool changed = true;
// for (int i = 0; i < cc.size(); i++) {
while (changed) {
changed = false;
for (int j = 0; j < m; j++) {
int x = u[j], y = v[j];
// if (cmp[x] == cmp[y]) continue;
if (dsu.find(x) == dsu.find(y)) continue;
// int ca = cmp[x], cb = cmp[y];
int ca = cmp[dsu.find(x)], cb = cmp[dsu.find(y)];
if (dsu.siz[dsu.find(x)] < dsu.siz[dsu.find(y)]) swap(ca, cb);
int req = c[j];
if (dsu.colour[dsu.find(head[ca])].count(req) && dsu.colour[dsu.find(head[cb])].count(req)) {
dsu.unite(head[ca], head[cb]);
exists[cb] = 0;
changed = true;
}
}
}
for (int i = 0; i < m; i++) {
// int ca = cmp[u[i]], cb = cmp[v[i]];
int x = dsu.find(u[i]), y = dsu.find(v[i]);
int ca = cmp[x], cb = cmp[y];
int req = c[i];
if (x == y) continue;
if (dsu.colour[x].count(req)) G3[ca].push_back(cb), deg[cb]++;
else if (dsu.colour[y].count(req)) G3[cb].push_back(ca), deg[ca]++;
}
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] = dsu.siz[dsu.find(head[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[dsu.find(i)] == mn;
return ans;
}
