#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <queue>
#include <random>
std::mt19937 rng(123);
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();
std::vector<bool> haveKey(n, false);
std::vector<std::vector<int>> unlock(n);
std::vector<bool> explored(n, false);
std::vector<bool> vis(n, false);
int m = (int) u.size();
std::vector<std::vector<std::pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
g[u[i]].push_back({v[i], c[i]});
g[v[i]].push_back({u[i], c[i]});
}
std::vector<int> answer(n, n + 1);
auto explore = [&](int start) { // un din asta am voie sa fac in O(n)
std::queue<int> reach; // nu cred ca e neaparat sa fac bfs dar trebuie sa resetez niste chestii la final si atunci cand fac bfs pot doar sa dau break si se amortizeaza sau ceva
reach.push(start);
vis[start] = true;
std::vector<int> visited;
bool early = false;
while (!reach.empty() && !early) {
int u = reach.front();
visited.push_back(u);
reach.pop();
if (explored[u]) {
early = true;
break;
}
int key = r[u];
for (const auto &[v, t] : g[u]) {
if (!vis[v]) {
if (haveKey[t]) {
if (explored[v]) {
early = true;
break;
}
reach.push(v);
vis[v] = true;
} else {
unlock[t].push_back(v);
}
}
}
if (haveKey[key]) {
continue;
}
haveKey[key] = true;
for (const auto &u : unlock[key]) {
if (!vis[u]) {
vis[u] = true;
reach.push(u);
if (explored[u]) {
early = true;
break;
}
}
}
unlock[key].clear();
}
if (!early) {
for (int u : visited) {
answer[u] = std::min(answer[u], (int) visited.size());
}
} else {
while (!reach.empty()) {
vis[reach.front()] = false;
reach.pop();
}
}
for (int u : visited) {
vis[u] = false;
haveKey[r[u]] = false;
for (const auto &[v, t] : g[u]) {
unlock[t].clear();
}
}
explored[start] = true;
};
std::vector<int> order;
for (int i = 0; i < m; i++) {
order.push_back(u[i]);
order.push_back(v[i]);
}
std::shuffle(order.begin(), order.end(), rng);
int mini = n + 1;
for (int u : order) {
if (!explored[u]) {
explore(u);
mini = std::min(mini, answer[u]);
}
}
for (int i = 0; i < n; i++) {
if (!explored[i]) {
explore(i);
mini = std::min(mini, answer[i]);
}
}
std::vector<int> ret(n);
for (int i = 0; i < n; i++) {
ret[i] = (answer[i] == mini);
}
return ret;
}
// astia sigur au teste proaste sau ceva ca nu are cum
// gen ??????????????
