#include <bits/stdc++.h>
using namespace std;
/*struct component {
int root;
set<int> keys;
void init(int u, int c) {
root = u;
keys.insert(c);
}
};*/
vector<int> find_reachable(vector<int> c, vector<int> u, vector<int> v, vector<int> r) {
int n = c.size();
int m = u.size();
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
g[u[i]].emplace_back(v[i], r[i]);
g[v[i]].emplace_back(u[i], r[i]);
}
vector<set<int>> keys(n);
vector<vector<int>> ch(n);
vector<int> id(n);
for (int i = 0; i < n; i++) {
//comp[i].init(i, c[i]);
keys[i].insert(c[i]);
ch[i] = {i};
id[i] = i;
}
vector<int> ans(n, 1e9);
vector<int> par(n);
for (int i = 0; i < n; i++) {
par[i] = i;
}
function<int(int)> root = [&](int u) {
return par[u] == u ? u : par[u] = root(par[u]);
};
function<void(int, int)> Merge = [&](int u, int v) {
int my_v = v;
u = root(u);
v = root(v);
if (ch[u].size() > ch[v].size()) swap(u, v);
keys[u].clear();
for (int i : ch[u]) {
ch[v].push_back(i);
id[i] = my_v;
}
ch[u].clear();
};
for (int foo = 0; foo < 30; foo++) {
vector<bool> mrg(n, false);
vector<bool> was(n, false);
map<int, vector<int>> mp;
set<int> s;
for (int i = 0; i < n; i++) {
if (mrg[id[i]] || ans[id[i]] != 1e9) {
continue;
}
int other = -1;
vector<int> vis;
mp.clear();
s.clear();
function<void(int)> Dfs = [&](int u) {
if (id[u] != id[i]) {
other = u;
return;
}
if (other != -1 || was[u]) {
return;
}
vis.push_back(u);
was[u] = true;
s.insert(c[u]);
for (auto x : mp[c[u]]) {
Dfs(x);
if (other != -1) {
return;
}
}
mp[c[u]].clear();
for (auto e : g[u]) {
if (s.find(e.second) != s.end()) {
Dfs(e.first);
if (other != -1) {
return;
}
} else {
mp[e.second].push_back(e.first);
}
}
};
Dfs(id[i]);
if (other == -1) {
for (int u : vis) {
ans[u] = vis.size();
}
} else {
Merge(id[i], id[other]);
mrg[id[i]] = true;
//mrg[id[other]] = true;
}
}
}
int mn = *min_element(ans.begin(), ans.end());
for (int i = 0; i < n; i++) {
ans[i] = (ans[i] == mn ? 1 : 0);
}
return ans;
}
