using namespace std;
#include<bits/stdc++.h>
#define vec vector
struct State {
map<int, vec<int>> locked_edgs;
vec<int> stk;
set<int> merged;
set<int> keys;
};
const int N = 300'005;
vec<pair<int, int>> g[N];
bool processed[N];
set<int> top;
int node_keys[N];
int ans[N];
State states[N];
void merge(int u, int v) {
if(states[u].merged.size() < states[v].merged.size()) swap(states[u], states[v]);
State& s1 = states[u];
State& s2 = states[v];
for(int u : s2.merged) {
s1.merged.insert(u);
}
for(int k : s2.keys) {
if(s1.locked_edgs.find(k) != s1.locked_edgs.end()) {
for(int v : s1.locked_edgs[k]) {
s1.stk.push_back(v);
}
s1.locked_edgs.erase(k);
}
s1.keys.insert(k);
}
for(auto edgs : s2.locked_edgs) {
int k = edgs.first;
if(s1.keys.find(k) != s1.keys.end()) {
for(int v : edgs.second) {
s1.stk.push_back(v);
}
}
else {
for(int v : edgs.second) {
s1.locked_edgs[k].push_back(v);
}
}
}
for(int u : s2.stk) {
s1.stk.push_back(u);
}
}
int dfs(int u) {
top.insert(u);
//TODO: IF this breaks it's because of this reference which might change after merge maybe??
State& state = states[u];
state.keys.insert(node_keys[u]);
state.merged.insert(u);
//cerr << "U: " << u << '\n';
for(auto edg : g[u]) {
int v = edg.first;
int k = edg.second;
if(state.keys.find(k) != state.keys.end()) state.stk.push_back(v);
else { state.locked_edgs[k].push_back(v); }
}
while(state.stk.size() > 0) {
int v = state.stk.back();
state.stk.pop_back();
//cerr << "V: " << v << '\n';
if(processed[v]) {
for(int w : state.merged) {
processed[w] = true;
}
//cerr << "HIT PROCESSED" << '\n';
return -1;
}
else if(state.merged.find(v) != state.merged.end()) {
//cerr << "IN MERGED" << '\n';
continue;
}
else if(top.find(v) != top.end()) {
//cerr << "AT TOP" << '\n';
return v;
}
else {
auto res = dfs(v);
if(res == -1) {
for(int w : state.merged) {
processed[w] = true;
}
//cerr << "DFS RETURNED LEAF FOUND" << '\n';
return -1;
}
else {
merge(u, v);
state = states[u];
if(state.merged.find(res) == state.merged.end()) {
//cerr << "MERGING IT UPWARDS" << '\n';
return res;
}
//cerr << "MERGED" << '\n';
}
}
}
//cerr << "IS A PREORDER LEAF" << '\n';
for(int v : state.merged) {
ans[v] = state.merged.size();
processed[v] = true;
}
return -1;
}
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();
int m = u.size();
for(int i = 0; i<n; i++) {
processed[i] = false;
g[i] = {};
ans[i] = n;
node_keys[i] = r[i];
states[i] = {};
}
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]});
}
for(int i = 0; i<n; i++) {
if(processed[i]) continue;
top = {};
auto res = dfs(i);
assert(processed[i]);
assert(res == -1);
}
int mn = n;
//cerr << "----DEBUG----" << '\n';
for(int i = 0; i<n; i++) {
mn = min(mn, ans[i]);
//cerr << ans[i] << ' ';
}
//cerr << '\n';
//cerr << "-------------" << '\n';
vec<int> res(n);
for(int i = 0; i<n; i++) {
res[i] = ans[i] == mn;
}
return res;
}
