#include <bits/stdc++.h>
using namespace std;
const int mx = 3e5 + 5;
class dsu {
public:
dsu(int n) {
p.resize(n, -1);
p2.resize(n);
for(int i = 0; i < n; i++)
p2[i] = i;
r.resize(n, 0);
}
int par(int x){
return p2[_par(x)];
}
void join(int a, int b){
a = _par(a); b = _par(b);
if (a == b) return;
p2[b] = p2[a];
if (r[a] < r[b]) swap(a, b);
if (r[a] == r[b]) r[a]++;
p[b] = a;
}
private:
int _par(int x){
return p[x] == -1 ? x : p[x] = _par(p[x]);
}
vector<int> p, r, p2;
} cc(0), group(0);//connected components, grouped nodes (cycle)
class node {
public:
node(int id, int key) : id(id), sz(1), r(0), curpath(-1){
nodes.push_back(id);
keys.insert(key);
}
node() : node(-1, -1){};
static void join(node &a, node &b) {
if (a.r < b.r){
swap(a, b);
swap(a.id, b.id);
}
if (a.r == b.r)
a.r++;
a.sz += b.sz;
group.join(a.id, b.id);
a.keys.insert(b.keys.begin(), b.keys.end());
a.nodes.insert(a.nodes.end(), b.nodes.begin(), b.nodes.end());
for (auto &x : b.paths){
if (a.keys.count(x.first)){
a.good.insert(a.good.end(), x.second.begin(), x.second.end());
}
else{
a.paths[x.first].insert(a.paths[x.first].end(), x.second.begin(), x.second.end());
}
}
for (auto &x : b.keys){
if (!a.paths.count(x))
continue;
a.good.insert(a.good.end(), a.paths[x].begin(), a.paths[x].end());
a.paths.erase(x);
}
}
inline int getPath() {
if(curpath != -1 && group.par(curpath) != group.par(id)) return group.par(curpath);
while (good.size() && group.par(good.back()) == group.par(id))
good.pop_back();
if (!good.size()) return -1;
int res = good.back();
good.pop_back();
curpath = res;
return group.par(res);
}
inline void addPath(int to, int key){
if(keys.count(key)) {
good.push_back(to);
}
else{
paths[key].push_back(to);
}
}
inline int getSize(){
return sz;
}
inline vector<int>& getNodes(){
return nodes;
}
private:
int sz, id, r, curpath; // rank ensures that at most logn times :DD
map<int, vector<int>> paths; // color, destination
vector<int> good; // paths that you have key to :D
vector<int> nodes; // everything in this node so we can output
set<int> keys; //list of keys
};
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
const int n = r.size();
const int m = u.size();
cc = dsu(n);
group = dsu(n);
std::vector<int> ans(n, 0);
vector<node> nodes(n);
vector<int> q;
vector<int> pot;
for (int i = 0; i < n; i++){
nodes[i] = node(i, r[i]);
q.push_back(i);
}
for (int i = 0; i < m; i++){
nodes[u[i]].addPath(v[i], c[i]);
nodes[v[i]].addPath(u[i], c[i]);
}
while(!q.empty()){
int t = q.back();
q.pop_back();
int p = nodes[t].getPath();
if(p == -1){
//no parent
//add to potential answers
pot.push_back(t);
}
else if(cc.par(t) == cc.par(p)){
//there is a cycle
//find cycle and merge and stuff
int tmp = p;
while(tmp != t && tmp != -1){
int tmp2 = nodes[tmp].getPath();
node::join(nodes[t], nodes[tmp]);
tmp = tmp2;
}
//no more par so put it back in the queue
q.push_back(t);
}
else {
cc.join(t, p);
}
}
int mn = n;
for(auto &x : pot) mn = min(mn, nodes[x].getSize());
for(auto &x : pot){
if(nodes[x].getSize() == mn){
for(auto &u : nodes[x].getNodes()){
ans[u] = 1;
}
}
}
return ans;
}
