#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi22/d2/debug.h"
#else
#define debug(...) void(37)
#endif
struct DSU {
vector<int> link;
DSU(int n) {
link.resize(n);
iota(link.begin(), link.end(), 0);
}
int get(int v) {
return link[v] = (link[v] != v ? get(link[v]) : v);
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) {
return false;
}
link[y] = x;
return true;
}
};
std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
int N = int(R.size());
int M = int(U.size());
vector<vector<int>> g(N);
for (int i = 0; i < M; ++i) {
g[V[i]].push_back(i);
g[U[i]].push_back(i);
}
DSU d(N);
vector<bool> act(N);
vector<bool> vis(N);
vector<vector<int>> blocked(N);
auto Expand = [&](int x) -> pair<vector<int>, int> {
int link = -1;
vector<int> verts;
auto Add_v = [&](int to) {
if (d.get(to) != d.get(x)) {
link = d.get(to);
} else if (!vis[to]) {
verts.push_back(to);
vis[to] = true;
act[R[to]] = true;
}
};
auto Add_e = [&](int id) {
Add_v(V[id]);
Add_v(U[id]);
};
Add_v(x);
for (int it = 0; it < int(verts.size()); ++it) {
int v = verts[it];
Add_v(v);
for (auto e : blocked[R[v]]) {
Add_e(e);
}
blocked[R[v]].clear();
for (auto id : g[v]) {
if (act[C[id]]) {
Add_e(id);
} else {
blocked[C[id]].push_back(id);
}
}
}
for (auto v : verts) {
act[R[v]] = false;
vis[v] = false;
for (auto id : g[v]) {
blocked[C[id]].clear();
}
}
return {verts, link};
};
while (true) {
bool update = false;
for (int i = 0; i < N; ++i) {
debug(i, d.get(i));
if (d.get(i) == i) {
auto[v, x] = Expand(i);
debug(i, x, v);
if (x != -1) {
update = true;
d.unite(x, i);
}
}
}
if (!update) {
break;
}
}
vector<int> ans;
int mn = N + 1;
for (int i = 0; i < N; ++i) {
if (d.get(i) == i) {
auto v = Expand(i).first;
int s = int(v.size());
if (s < mn) {
ans.clear();
mn = s;
}
if (s == mn) {
ans.insert(ans.end(), v.begin(), v.end());
}
}
}
vector<int> ret(N);
for (auto v : ans) {
ret[v] = true;
}
return ret;
}
