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;
};
State& merge(State& s1, State& s2) {
if(s1.merged.size() < s2.merged.size()) swap(s1, s2);
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);
}
return s1;
}
pair<int, State> dfs(int u, set<int>& top, vec<bool>& processed, vec<vec<pair<int, int>>>& g, vec<int>& node_keys, vec<int>& ans) {
top.insert(u);
State state{};
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, state};
}
else {
auto res = dfs(v, top, processed, g, node_keys, ans);
if(res.first == -1) {
for(int w : state.merged) {
processed[w] = true;
}
cerr << "DFS RETURNED LEAF FOUND" << '\n';
return {-1, {}};
}
else {
State new_state = move(merge(state, res.second));
state = move(new_state);
if(state.merged.find(res.first) == state.merged.end()) {
cerr << "MERGING IT UPWARDS" << '\n';
return {res.first, move(state)};
}
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();
vec<vec<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]});
}
vec<bool> processed(n);
vec<int> ans(n, n);
for(int i = 0; i<n; i++) {
if(processed[i]) continue;
set<int> top;
auto res = dfs(i, top, processed, g, r, ans);
assert(processed[i]);
assert(res.first == -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';
for(int i = 0; i<n; i++) {
ans[i] = ans[i] == mn;
}
return ans;
}
