#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;
int n, m;
vector<ar<int, 2>> adj[N];
int par[N], sz[N];
set<int> cols[N]; // the colors that the current node contains
int f[N]; // parent of tree
int up[N]; // root of tree
int vis[N];
set<int> roots; // set of all roots
int find_set(int v) {
return par[v] == v ? v : par[v] = find_set(par[v]);
}
// stuff to update:
// - cols
// - roots
// - if stuff is unioned, it can't be dead
// - adj
int union_sets(int a, int b) {
a = find_set(a), b = find_set(b);
if (a == b) return -1;
if (sz[a] < sz[b]) swap(a, b);
par[b] = a, sz[a] += sz[b], sz[b] = 0;
roots.erase(b), roots.insert(a);
for (int x : cols[b]) cols[a].insert(x);
for (auto nxt : adj[b]) adj[a].push_back(nxt);
adj[b].clear(), cols[b].clear();
return a;
}
int recalc_up(int c) {
if (up[c] != -1) return up[c];
return up[c] = recalc_up(f[c]);
}
vector<int> find_reachable(vector<int> r, vector<int> _u, vector<int> _v, vector<int> _c) {
n = sz(r), m = sz(_c);
for (int i = 0; i < m; i++) {
int a = _u[i], b = _v[i], x = _c[i];
adj[a].push_back({b, x});
adj[b].push_back({a, x});
}
std::iota(par, par + n, 0);
std::fill(sz, sz + n, 1);
for (int i = 0; i < n; i++) {
cols[i].insert(r[i]);
roots.insert(i);
}
set<int> done;
while (sz(roots)) {
for (int c : roots) {
assert(c == find_set(c));
f[c] = -1;
for (auto [nxt, x] : adj[c]) if (find_set(nxt) != find_set(c) && cols[c].count(x)) {
f[c] = find_set(nxt);
break;
}
if (f[c] == -1) done.insert(c);
else if (done.count(find_set(f[c]))) {
f[c] = -1;
}
vis[c] = -1;
up[c] = c;
}
set<int> cyc_root;
for (int c : roots) if (!done.count(c) && vis[c] == -1) {
bool mark = 0;
int cur = c;
while (vis[cur] == -1) {
vis[cur] = c;
if (f[cur] == -1) {
mark = 1;
break;
}
cur = find_set(up[f[cur]]);
}
if (mark) { // can reach a dead thing, so must be killed
int start = c;
while (start != cur) {
int nxt = f[start];
f[start] = -1;
start = find_set(nxt);
}
continue;
}
if (vis[cur] == c) {
cyc_root.insert(cur);
}
}
map<int, int> cyc; // node, cyc root
for (int c : cyc_root) {
cyc[c] = c;
int cur = find_set(f[c]);
while (cur != c) {
cyc[cur] = c;
cur = find_set(f[cur]);
}
}
// recalculate up
vector<int> dead_roots;
for (int c : roots) if (!cyc.count(c)) {
dead_roots.push_back(c);
up[c] = -1;
}
for (int c : dead_roots) {
if (f[c] != -1) {
recalc_up(c);
}
roots.erase(c);
}
// merge the new roots
for (auto [a, b] : cyc) {
union_sets(a, b);
}
}
int ret = n + 1;
for (int c : done) {
assert(c == find_set(c));
ret = min(ret, sz[c]);
}
vector<int> ans(n);
for (int i = 0; i < n; i++) if (done.count(find_set(i)) && sz[find_set(i)] == ret) ans[i] = 1;
return ans;
}
