#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, m;
int vis[N];
int nxt[N];
vector<int> city_key;
vector<pair<int, int>> g[N];
int p2[N], sz2[N];
bool valid[N];
int p[N], sz[N];
vector<int> nodes[N];
set<int> active_keys[N];
set<int> owned_colors[N];
set<int> needed_colors[N];
set<pair<int, int>> inactive_key[N];
int get2(int v) {
return p2[v] = (p2[v] == v ? v : get2(p2[v]));
}
void unite2(int u, int v) {
u = get2(u);
v = get2(v);
if (u == v) {
return;
}
if (sz2[u] > sz2[v]) swap(u, v);
sz2[v] += sz2[u];
p2[u] = v;
}
void init_dsu2() {
for (int i = 0; i < n; ++i) {
p2[i] = i;
sz[i] = 1;
}
for (int i = 0; i < n; ++i) {
unite2(i, nxt[i]);
}
}
void init_dsu() {
for (int i = 0; i < n; ++i) {
p[i] = i;
sz[i] = 1;
nodes[i].push_back(i);
owned_colors[i].insert(city_key[i]);
for (auto [u, edge_key] : g[i]) {
if (edge_key == city_key[i] && u != nxt[i]) {
active_keys[i].insert(u);
} else if (edge_key != city_key[i]) {
needed_colors[i].insert(edge_key);
inactive_key[i].insert({edge_key, u});
}
}
}
}
int get(int v) {
return p[v] = (p[v] == v ? v : get(p[v]));
}
void unite(int u, int v) {
u = get(u);
v = get(v);
if (u == v) {
return;
}
if (sz[u] > sz[v]) {
swap(u, v);
}
sz[v] += sz[u];
p[u] = v;
for (int w : nodes[u]) {
nodes[v].push_back(w);
}
for (auto w : active_keys[u]) {
active_keys[v].insert(w);
}
for (auto c : owned_colors[u]) {
if (owned_colors[v].count(c)) {
continue;
}
while (true) {
auto it = inactive_key[v].lower_bound({c, 0});
if (it == inactive_key[v].end() || it->first != c) {
break;
}
active_keys[v].insert(it->second);
inactive_key[v].erase(it);
}
owned_colors[v].insert(c);
}
for (auto c : needed_colors[u]) {
if (!owned_colors[v].count(c)) {
needed_colors[v].insert(c);
continue;
}
while (true) {
auto it = inactive_key[u].lower_bound({c, 0});
if (it == inactive_key[u].end() || it->first != c) {
break;
}
active_keys[v].insert(it->second);
inactive_key[u].erase(it);
}
}
for (auto [c, w] : inactive_key[u]) {
inactive_key[v].insert({c, w});
}
valid[v] = true;
}
vector<int> find_reachable(vector<int> r, vector<int> u_, vector<int> v_, vector<int> c) {
city_key = r;
n = (int) city_key.size();
m = (int) u_.size();
for (int i = 0; i < m; ++i) {
g[u_[i]].push_back({v_[i], c[i]});
g[v_[i]].push_back({u_[i], c[i]});
}
vector<int> ans(n);
bool ok = true;
for (int v = 0; v < n; ++v) {
bool f = false;
for (auto [u, edge_key] : g[v]) {
if (edge_key == city_key[v]) {
nxt[v] = u;
f = true;
}
}
if (!f) {
ok = false;
ans[v] = 1;
}
}
if (!ok) {
return ans;
}
init_dsu2();
init_dsu();
vector<int> stk;
function<void(int)> dfs = [&](int v) {
if (vis[v] == 2) {
return;
}
if (vis[v] == 1) {
assert(get(v) == v);
valid[v] = true;
while (stk.back() != v) {
int top = stk.back();
stk.pop_back();
unite(top, v);
}
return;
}
vis[v] = 1;
stk.push_back(v);
dfs(nxt[v]);
if (!stk.empty() && stk.back() == v) {
stk.pop_back();
}
vis[v] = 2;
};
for (int i = 0; i < n; ++i) {
dfs(i);
}
set<int> roots;
for (int i = 0; i < n; ++i) {
if (get(i) == i && valid[i] == true) {
roots.insert(i);
}
}
while (!roots.empty()) {
int root = *roots.begin();
roots.erase(root);
assert(get(root) == root);
vector<int> toErase;
for (auto u : active_keys[root]) {//make sure this iterates over everything.
if (get2(u) == get2(root)) {
int x = u;
while (get(x) != get(root)) {
unite(x, root);
x = nxt[x];
}
toErase.push_back(u);
} else {
toErase.push_back(u);
unite2(u, root);
valid[root] = false;
nxt[root] = get(u);
break;
}
}
for (int u : toErase) {
active_keys[root].erase(u);
}
}
int mn = n;
for (int i = 0; i < n; ++i) {
if (get(i) != i || !valid[i]) {
continue;
}
mn = min(mn, sz[i]);
}
for (int i = 0; i < n; ++i) {
if (sz[get(i)] == mn) {
ans[i] = 1;
}
}
return ans;
}
