#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>;
/*
if ever there is a node with colour r[i] and no adjacent edges with colour r[i] the answer is trivially 0
so wlog every node has at least 1 edge with colour = r[i]
this implies a directed cyclic graph G
imagine we have some directed Acyclic graph R, representing the strongly connected components of G
then we can compute |reachable set from u| = |scc of u| + Σdp[v] for all v in R that scc[u] has an edge to r
now the question is how to find the complete graph R (just calculating scc isn't enough, bc we dont count the case
where scc[u] has colour c[i] and so does scc[v], but neither u nor v have colour c[i])
concept: while there has been a merge, iterate over all the edges of the original graph, if the condition ^^^ happened,
then merge scc[u] and scc[v] (using dsu for small to large merging etc works nicely)
then finally for every edge where scc[u] has c[i] or scc[v] has c[i] but only 1 of them, add that simple directed edge to R
this is guaranteed to produce the full accurate graph R, which we can then do dp on
the question now is time complexity. obviously its <= m^2 + mlogn (mlogn from small to large) but to my surprise submitting
the supposedly O(m^2) code passed with ease on the largest subtask (no contraints, n,m <= 300k) and so clearly there are far
far far less than O(m) merging loops
editorial says there is O(logn) merging loops total, i cant prove it either way but its obvious to say that every edge satisfying the
condition i described merges two components of size (2) (on the first loop). now i claim that if an edge causes a merge on
the i+1th iteration, it *could not* have caused a merge on any loop iteration <= i. this implies it occured between 2 components
that were merged in loop iteration i, and every loop iteration must at least double the size of eveyr component involved,
and so what it means is that every iteration we have to have halved the number of remaining components
idk if that argument holds up but it sounds reasonable as an explanation in hindsight (would not have thought about it in contest
probably lol)
*/
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[cmp[dsu.find(i)]] == mn;
return ans;
}
