#include <bits/stdc++.h>
struct Dsu {
std::vector <int> p;
std::vector <int> size;
Dsu(int s) {
p.resize(s);
std::iota(p.begin(), p.end(), 0);
size.resize(s, 1);
}
int find(int v) {
return v == p[v] ? v : (p[v] = find(p[v]));
}
void unite(int u, int v) {
if ((u = find(u)) == (v = find(v))) {
return;
}
if (size[u] > size[v]) {
p[v] = u;
} else {
p[u] = v;
}
}
};
struct Edge {
int u, v, c;
};
int n, m;
std::vector <Edge> ed;
std::vector <std::vector <int>> g;
std::vector <int> p;
Dsu dsu(0), tree(0);
std::vector <int> r;
bool go() {
//std::vector <std::vector <int>> in(n);
//for (int i = 0; i < n; i++) {
//in[dsu.find(i)].push_back(i);
//}
//std::vector <std::vector <int>> ed_of(n);
//for (int i = 0; i < n; i++) {
//if (dsu.find(i) != i || p[i] != -1) {
//continue;
//}
//for (int x : in[i]) {
//}
//}
std::vector <std::set <int>> keys(n);
for (int i = 0; i < n; i++) {
keys[dsu.find(i)].insert(r[i]);
}
std::vector <std::vector <int>> eds(n);
for (int i = 0; i < n; i++) {
for (int x : g[i]) {
if (keys[dsu.find(i)].count(ed[x].c)) {
eds[dsu.find(i)].push_back(ed[x].u ^ ed[x].v ^ i);
}
}
}
bool did = false;
for (int i = 0; i < n; i++) {
int v = dsu.find(i);
if (p[v] != -1) {
continue;
}
if (dsu.find(i) != i) {
continue;
}
for (int x : eds[v]) {
if (dsu.find(x) == v) {
continue;
}
did = true;
if (tree.find(x) == tree.find(v)) {
int to = dsu.find(x);
while (v != to) {
int new_to = dsu.find(p[to]);
p[v] = p[to] = p[v];
dsu.unite(to, v);
v = dsu.find(v);
to = new_to;
}
} else {
p[v] = dsu.find(x);
tree.unite(x, v);
break;
}
}
}
return did;
}
std::vector <int> find_reachable(std::vector <int> _r, std::vector <int> u, std::vector <int> v, std::vector <int> c) {
r = _r;
n = r.size();
m = c.size();
ed.resize(m);
g.resize(n);
for (int i = 0; i < m; i++) {
g[u[i]].push_back(i);
g[v[i]].push_back(i);
ed[i] = { u[i], v[i], c[i] };
}
p.resize(n, -1);
dsu = Dsu(n);
tree = Dsu(n);
while (go());
std::vector <int> ans(n, 0);
for (int i = 0; i < n; i++) {
ans[dsu.find(i)] += p[dsu.find(i)] == -1;
}
int res = 1 << 30;
for (int x : ans) {
if (x) {
res = std::min(res, x);
}
}
std::vector <int> ret(n, 0);
for (int i = 0; i < n; i++) {
if (ans[dsu.find(i)] == res) {
ret[i] = 1;
}
}
return ret;
}
