#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
vector<int> data;
explicit UnionFind(const int n) : data(n, -1) {}
int find(const int x) {
return data[x] < 0 ? x : data[x] = find(data[x]);
}
int merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
if (data[x] > data[y]) {
swap(x, y);
}
data[x] += data[y];
data[y] = x;
}
return x;
}
};
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
const int N = (int)size(R);
const int M = (int)size(C);
struct Data {
vector<int> open;
set<int> keys;
map<int, vector<int>> locked;
void add_edge(const int u, const int k) {
if (keys.find(k) != end(keys)) {
open.push_back(u);
} else {
locked[k].push_back(u);
}
}
void add_key(const int x) {
if (const auto itr = locked.find(x); itr != end(locked)) {
for (const int u : itr->second) {
open.push_back(u);
}
locked.erase(itr);
}
keys.insert(x);
}
};
UnionFind cycle(N);
vector<Data> data(N);
vector<int> status(N), toward(N), reach(N, N + 1);
for (int i = 0; i < N; ++i) {
data[i].keys.insert(R[i]);
}
for (int i = 0; i < M; ++i) {
data[U[i]].add_edge(V[i], C[i]);
data[V[i]].add_edge(U[i], C[i]);
}
for (int u = 0; u < N; ++u) {
if (status[u] == 1) {
continue;
}
vector<int> list;
while (true) {
if (status[u] == 1) {
break;
}
if (status[u] == 0) {
status[u] = -1;
list.push_back(u);
}
if (data[u].open.empty()) {
vector<int> same;
for (const int x : list) {
if (cycle.find(x) == u) {
same.push_back(x);
}
}
const int n = (int)size(same);
for (const int x : same) {
reach[x] = n;
}
break;
}
toward[u] = cycle.find(data[u].open.back());
data[u].open.pop_back();
if (status[toward[u]] == -1) {
int v = u;
while (true) {
v = cycle.find(toward[v]);
if (v == u) {
break;
}
const int r = cycle.merge(u, v);
const auto& move = data[r == u ? v : u];
u = r;
for (const int x : move.open) {
data[u].open.push_back(x);
}
for (const int x : move.keys) {
data[u].add_key(x);
}
for (const auto& [k, vec] : move.locked) {
for (const int x : vec) {
data[u].add_edge(x, k);
}
}
}
} else {
u = toward[u];
}
}
for (const int v : list) {
status[v] = 1;
}
}
const int min = *min_element(begin(reach), end(reach));
vector<int> ret(N);
for (int i = 0; i < N; ++i) {
ret[i] = min == reach[i];
}
return ret;
}
