#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
// https://mzhang2021.github.io/cp-blog/library/
struct SCC {
int n, ti;
std::vector<int> num, id, stk;
std::vector<std::vector<int>> adj, dag, comp;
std::vector<int> root;
SCC(int _n) : n(_n), ti(0), num(n), id(n, -1), adj(n), root(n) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
void build() {
for (int u=0; u<n; u++)
if (!num[u])
dfs(u);
dag.resize(comp.size());
for (auto &c : comp)
for (int u : c)
for (int v : adj[u])
if (id[u] != id[v])
dag[id[u]].push_back(id[v]);
for (auto &v : dag) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
for (auto v : comp) {
for (int x : v) {
root[x] = v[0];
}
}
}
int dfs(int u) {
int low = num[u] = ++ti;
stk.push_back(u);
for (int v : adj[u]) {
if (!num[v])
low = std::min(low, dfs(v));
else if (id[v] == -1)
low = std::min(low, num[v]);
}
if (low == num[u]) {
comp.emplace_back();
do {
id[stk.back()] = (int) comp.size() - 1;
comp.back().push_back(stk.back());
stk.pop_back();
} while (comp.back().back() != u);
}
return low;
}
};
std::vector<int> find_reachable(std::vector<int> a, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
int n = (int) a.size();
int m = (int) U.size();
U.resize(2 * m);
V.resize(2 * m);
C.resize(2 * m);
for (int i = m; i < 2 * m; i++) {
U[i] = V[i - m];
V[i] = U[i - m];
C[i] = C[i - m];
}
m *= 2;
std::vector<int> root(n);
for (int i = 0; i < n; i++) {
root[i] = i;
}
for (int phase = 0; phase < 20; phase++) {
std::vector<std::set<int>> keys(n);
for (int i = 0; i < n; i++) {
keys[root[i]].insert(a[i]);
}
SCC g(n);
for (int i = 0; i < m; i++) {
int u = U[i], v = V[i];
int c = C[i];
if (root[u] == root[v] || keys[root[u]].count(c)) {
g.addEdge(u, v);
}
}
g.build();
for (int i = 0; i < n; i++) {
root[i] = g.root[i];
}
}
std::vector<int> sz(n, 0);
for (int i = 0; i < n; i++) {
sz[root[i]]++;
}
std::vector<bool> hasOut(n, false);
std::vector<std::set<int>> keys(n);
for (int i = 0; i < n; i++) {
keys[root[i]].insert(a[i]);
}
for (int i = 0; i < m; i++) {
int u = U[i], v = V[i];
int c = C[i];
if (root[u] != root[v] && keys[root[u]].count(c)) {
hasOut[root[u]] = true;
}
}
int minSize = n;
for (int i = 0; i < n; i++) {
if (!hasOut[root[i]]) {
minSize = std::min(minSize, sz[root[i]]);
}
}
std::vector<int> ret(n, 0);
for (int i = 0; i < n; i++) {
if (!hasOut[root[i]]) {
if (sz[root[i]] == minSize) {
ret[i] = 1;
}
}
}
return ret;
}
