#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <vector>
struct UnionFind {
UnionFind(int n) : uf(n) { std::iota(uf.begin(), uf.end(), 0); }
int Find(int x) {
if (x == uf[x]) return x;
return uf[x] = Find(uf[x]);
}
void Merge(int x, int y) {
int fx = Find(x), fy = Find(y);
uf[fx] = fy;
}
std::vector<int> uf;
};
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u,
std::vector<int> v, std::vector<int> c) {
int N = r.size(), M = u.size();
std::vector<std::unordered_set<int>> keys(N + N);
std::vector<std::unordered_map<int, std::vector<int>>> out_edges(N + N);
std::vector<std::vector<int>> good_edges(N + N);
std::vector<int> sz_v(N + N), sz_e(N + N);
std::vector<int> to(N + N, -1);
for (int i = 0; i < N; ++i) {
keys[i].insert(r[i]);
sz_v[i] = 1;
}
for (int i = 0; i < M; ++i) {
for (int x : {u[i], v[i]}) {
sz_e[x]++;
if (r[x] == c[i]) {
good_edges[x].push_back(i);
} else {
out_edges[x][c[i]].push_back(i);
}
}
}
int K = N;
UnionFind conn(N + N), repr(N + N);
std::vector<int> res;
for (int i = 0; i < K; ++i) {
while (!good_edges[i].empty()) {
int e = good_edges[i].back();
if (repr.Find(u[e]) == repr.Find(v[e])) {
good_edges[i].pop_back();
} else {
break;
}
}
if (good_edges[i].empty()) {
// std::cerr << "stop i = " << i << "\n";
res.push_back(i);
continue;
}
int e = good_edges[i].back();
int x = repr.Find(u[e]), y = repr.Find(v[e]);
assert(x == i || y == i);
if (x != i) {
std::swap(x, y);
}
// std::cerr << "x = " << x << " y = " << y << std::endl;
to[x] = y;
if (conn.Find(x) == conn.Find(y)) {
std::vector<int> cycle;
int t = i;
do {
// std::cerr << "t = " << t << std::endl;
cycle.push_back(t);
assert(to[t] != -1);
t = repr.Find(to[t]);
} while (t != i);
int p = K++;
for (int t : cycle) {
sz_v[p] += sz_v[t];
if (sz_e[p] < sz_e[t]) {
keys[p].swap(keys[t]);
out_edges[p].swap(out_edges[t]);
good_edges[p].swap(good_edges[t]);
}
sz_e[p] += sz_e[t];
good_edges[p].insert(good_edges[p].end(), good_edges[t].begin(),
good_edges[t].end());
for (int k : keys[t]) {
if (keys[p].find(k) == keys[p].end()) {
keys[p].insert(k);
if (out_edges[p].find(k) != out_edges[p].end()) {
good_edges[p].insert(good_edges[p].end(), out_edges[p][k].begin(),
out_edges[p][k].end());
out_edges[p].erase(k);
}
}
}
for (auto iter : out_edges[t]) {
int k = iter.first;
if (keys[p].find(k) != keys[p].end()) {
good_edges[p].insert(good_edges[p].end(), iter.second.begin(),
iter.second.end());
} else {
out_edges[p][k].insert(out_edges[p][k].end(), iter.second.begin(),
iter.second.end());
}
}
repr.Merge(t, p);
}
} else {
conn.Merge(x, y);
}
}
int min_sz = N + 1;
for (int u : res) {
assert(repr.Find(u) == u);
min_sz = std::min(min_sz, sz_v[u]);
}
std::vector<bool> opt(N + N);
for (int u : res) {
if (sz_v[u] == min_sz) {
opt[u] = true;
}
}
std::vector<int> ans(N);
for (int i = 0; i < N; ++i) {
if (opt[repr.Find(i)]) {
ans[i] = 1;
}
}
return ans;
}
