#include <bits/stdc++.h>
using namespace std;
vector<int> find_reachable(vector<int> city_key, vector<int> u_, vector<int> v_, vector<int> c) {
int n = (int) city_key.size();
int m = (int) u_.size();
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; ++i) {
int u = u_[i], v = v_[i], edge_key = c[i];
g[u].emplace_back(v, edge_key);
g[v].emplace_back(u, edge_key);
}
int idd = n;
vector<vector<int>> t(n), rt(n);
auto add_edge = [&](int u, int v) {
t[u].push_back(v);
rt[v].push_back(u);
};
for (int current_key = 0; current_key < 30; ++current_key) {//build graph t, rt
vector<bool> vis(n);
function<void(int, int)> dfs = [&](int v, int p) {
//cout << "p, v: " << p << ' ' << v << endl;
vis[v] = true;
add_edge(p, v);
if (city_key[v] == current_key) {
add_edge(v, p);
}
for (auto [u, edge_key] : g[v]) {
if (edge_key == current_key && !vis[u]) {
dfs(u, p);
}
}
};
for (int v = 0; v < n; ++v) {
if (!vis[v]) {
t.push_back({});
rt.push_back({});
dfs(v, idd++);
}
}
}
vector<int> stk, vis(idd);
function<void(int)> dfs = [&](int v) {
vis[v] = true;
for (int u : t[v]) {
if (!vis[u]) {
dfs(u);
}
}
stk.push_back(v);
};
for (int i = 0; i < idd; ++i) {//find dfs order
if (!vis[i]) {
dfs(i);
}
}
vector<int> sz(idd);
vector<vector<int>> sccg(idd);
function<void(int, int)> dfs2 = [&](int v, int comp) {//build sccg & find sizes
vis[v] = comp;
sz[comp] += v < n;
for (int u : rt[v]) {
if (vis[u] == -1) {
dfs2(u, comp);
} else if (vis[u] != vis[v]) {
//cout << "u, v, visu, visv: " << u << ' ' << v << ' ' << vis[u] << ' ' << vis[v] << '\n';
sccg[vis[u]].push_back(vis[v]);
}
}
};
assert((int) stk.size() == idd);
int comp = 0;
for (int i = 0; i < idd; ++i) {
vis[i] = -1;
}
for (int i = idd - 1; i >= 0; --i) {
int v = stk[i];
if (vis[v] == -1) {
dfs2(v, comp++);
}
}
//for (int i = 0; i < n; ++i) {
//cout << "v, comp: " << i << ' ' << vis[i] << ' ' << sz[vis[i]] << '\n';
//}
vector<bool> vis2(comp);
function<void(int)> dfs3 = [&](int v) {//get subtree sizes
vis2[v] = true;
for (int u : sccg[v]) {
if (!vis2[u]) {
dfs3(u);
}
sz[v] += sz[u];
}
};
for (int i = 0; i < comp; ++i) {
if (!vis2[i]) {
sort(sccg[i].begin(), sccg[i].end());
sccg[i].resize(unique(sccg[i].begin(), sccg[i].end()) - sccg[i].begin());
dfs3(i);
}
}
int mn = n;
for (int i = 0; i < n; ++i) {
//cout << "i, comp, sz: " << i << ' ' << vis[i] << ' ' << sz[vis[i]] << '\n';
mn = min(mn, sz[vis[i]]);
}
//cout << "W" << endl;
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
if (sz[vis[i]] == mn) {
ans[i] = 1;
}
}
return ans;
}
