#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
struct DSU {
vt<int> uf, root;
DSU(const int n) : uf(n, -1), root(n) { iota(all(root), 0); }
int find(const int i) { return uf[i] < 0 ? i : uf[i] = find(uf[i]); }
int get_root(const int i) { return root[find(i)]; }
void unite(int a, int b) {
if ((a = find(a)) == (b = find(b)))
return;
if (uf[a] > uf[b])
swap(a, b), swap(root[a], root[b]);
uf[a] += uf[b];
uf[b] = a;
root[b] = root[a];
}
};
vt<int> find_reachable(const vt<int> R, const vt<int> U, const vt<int> V, const vt<int> C) {
const int N = size(R), M = size(U);
vt<vt<ari2>> adj(N);
FOR(i, 0, M - 1) {
adj[U[i]].push_back({V[i], C[i]});
adj[V[i]].push_back({U[i], C[i]});
}
DSU uf(N);
bool flag = true;
unordered_set<int> ans, p_ans;
const auto check = [&](const int x, const bool ret_option) {
vt<int> seen(N), key(N);
vt<vt<int>> blocked(N);
queue<int> qu;
qu.push(x);
seen[x] = key[R[x]] = 1;
while (size(qu)) {
const int i = qu.front();
qu.pop();
if (!ret_option)
p_ans.insert(i);
for (const auto &[j, c] : adj[i]) {
if (seen[j])
continue;
if (key[c]) {
if (uf.find(j) != uf.find(x)) {
assert(ret_option);
return uf.find(j);
}
qu.push(j);
seen[j] = key[R[j]] = 1;
} else {
blocked[c].push_back(j);
}
}
for (const auto &j : blocked[R[i]])
if (!seen[j]) {
if (uf.find(j) != uf.find(x)) {
assert(ret_option);
return uf.find(j);
}
seen[j] = key[R[j]] = 1;
qu.push(j);
}
blocked[R[i]].clear();
}
return -1;
};
while (flag) {
flag = false;
vt<ari2> pairs;
FOR(i, 0, N - 1) {
if (uf.find(i) != i)
continue;
const int j = check(i, 1);
if (j >= 0)
pairs.push_back({i, j}), flag = true;
}
for (const auto &[a, b] : pairs)
uf.unite(b, a);
}
int cur = INT_MAX;
FOR(i, 0, N - 1) {
if (uf.get_root(i) != i)
continue;
check(i, 0);
if (size(p_ans) < cur)
ans.clear();
if (size(p_ans) <= cur)
cur = size(p_ans), ans.insert(all(p_ans));
p_ans.clear();
}
vt<int> ret(N);
for (const auto &i : ans)
ret[i] = 1;
return ret;
}
