#include <bits/stdc++.h>
using namespace std;
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
const int n = r.size(), m = u.size();
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < m; ++i) {
adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});
}
const int max_color = 30;
auto reachable = [&](int u) {
vector<bool> have(max_color);
vector<vector<int>> traverse_with(max_color);
vector<bool> vis(n);
queue<int> q;
auto flush = [&](int k) {
if (!have[k]) {
return;
}
while (!traverse_with[k].empty()) {
q.push(traverse_with[k].back());
traverse_with[k].pop_back();
}
};
q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
have[r[u]] = true, flush(r[u]);
for (auto &[i, idx] : adj[u]) {
traverse_with[c[idx]].push_back(i), flush(c[idx]);
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += vis[i];
}
return ans;
};
auto vein_of = [&](int u) {
set<int> vis;
queue<int> q;
q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
if (vis.contains(u)) {
continue;
}
vis.insert(u);
for (auto &[i, idx] : adj[u]) {
if (r[u] == c[idx]) {
q.push(i);
}
}
}
return vector<int>(vis.begin(), vis.end());
};
vector<int> val(n, -1);
for (int i = 0; i < n; ++i) {
if (val[i] != -1) {
continue;
}
auto nodes = vein_of(i);
val[i] = reachable(i);
for (int &u : nodes) {
if (r[u] == r[i]) {
val[u] = val[i];
}
}
}
int mn = *min_element(val.begin(), val.end());
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
if (val[i] == mn) {
ans[i] = 1;
}
}
return ans;
}
#ifdef MACOS_LOCAL
#include "grader.cpp"
#endif
