#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<vector<int>> ch(n);
vector<int> id(n);
for (int i = 0; i < n; i++) {
//comp[i].init(i, c[i]);
ch[i] = {i};
id[i] = i;
}
vector<int> ans(n, 1e9);
vector<int> par(n);
vector<int> comp(n);
for (int i = 0; i < n; i++) {
par[i] = i;
comp[i] = i;
}
function<int(int)> who = [&](int u) {
return par[u] == u ? u : par[u] = who(par[u]);
};
function<int(int)> root = [&](int u) {
return comp[u] == u ? u : comp[u] = root(comp[u]);
};
function<void(int, int)> Merge = [&](int u, int v) {
int my_u = u;
int my_v = v;
u = who(u);
v = who(v);
if (ch[u].size() > ch[v].size()) swap(u, v);
for (int i : ch[u]) {
ch[v].push_back(i);
id[i] = my_v;
}
ch[u].clear();
par[u] = v;
comp[my_u] = my_v;
};
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[root(i)] || ans[root(i)] != 1e9) {
continue;
}
int other = -1;
vector<int> vis;
mp.clear();
s.clear();
function<void(int)> Dfs = [&](int u) {
if (root(u) != root(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(root(i));
if (other == -1) {
for (int u : vis) {
ans[u] = vis.size();
}
} else {
Merge(root(i), root(other));
mrg[root(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;
}
