#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
// https://mzhang2021.github.io/cp-blog/library/
struct SCC {
int n;
std::vector<std::vector<int>> g, gg;
std::vector<int> order, cur;
std::vector<bool> vis;
std::vector<int> root;
void init(int _n) {
n = _n;
g.resize(n);
gg.resize(n);
vis.assign(n, false);
root.resize(n);
order.clear();
cur.clear();
for (int i = 0; i < n; i++) {
g[i].clear();
gg[i].clear();
}
}
void addEdge(int u, int v) {
g[u].push_back(v);
gg[v].push_back(u);
}
void dfs0(int u) {
vis[u] = true;
for (int v : g[u]) {
if (!vis[v]) {
dfs0(v);
}
}
order.push_back(u);
}
void dfs(int u) {
vis[u] = true;
cur.push_back(u);
for (int v : gg[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
void build() {
vis.assign(n, false);
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs0(i);
}
}
vis.assign(n, false);
std::reverse(order.begin(), order.end());
for (int u : order) {
if (!vis[u]) {
cur.clear();
dfs(u);
for (int v : cur) {
root[v] = cur[0];
}
}
}
}
};
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;
}
SCC g;
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]);
}
g.init(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;
}
