#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
using namespace std;
#ifndef wambule
// #include ".h"
#else
#endif
const int N = 300005;
struct vert {
vert() {
next = -1;
size = 1;
}
set<pair<int, int> > locked;
set<int> keys;
set<int> unlocked;
set<int> vertices;
int next, size;
void add_key(int key) {
if(keys.find(key) != keys.end()) return;
for(;;) {
auto it = locked.lower_bound({key, 0});
if(it == locked.end() || (*it).first != key) break;
unlocked.insert((*it).second);
locked.erase(it);
}
keys.insert(key);
}
void add_edge(int x, int y) {
if(keys.find(y) != keys.end()) {
unlocked.insert(x);
} else {
locked.insert({y, x});
}
}
};
int n, m;
int up[N], up2[N];
vert vx[N];
queue<int> evolution;
vector<int> done;
int P(int x) {
return (up[x] < 0 ? x : up[x] = P(up[x]));
}
int P2(int x) {
return (up2[x] < 0 ? x : up2[x] = P2(up2[x]));
}
int Sz(int x) {
return -up[P(x)];
}
void merge(int x, int y) {
if(vx[x].size < vx[y].size) {
swap(vx[x], vx[y]);
}
up2[P2(y)] = P2(x);
vx[x].size += vx[y].size;
for(auto key : vx[y].keys) {
vx[x].add_key(key);
}
for(auto edge : vx[y].locked) {
vx[x].add_edge(edge.second, edge.first);
}
for(auto vertex : vx[y].unlocked) {
vx[x].unlocked.insert(vertex);
}
for(auto vertex : vx[y].vertices) {
vx[x].vertices.insert(vertex);
}
}
void activate(int x) {
x = P2(x);
while(vx[x].unlocked.size() && P2(*vx[x].unlocked.begin()) == x) {
vx[x].unlocked.erase(vx[x].unlocked.begin());
}
if(!vx[x].unlocked.size()) {
done.push_back(x);
return;
}
int y = P2(*vx[x].unlocked.begin());
if(P(x) != P(y)) {
up[P(x)] = P(y);
vx[x].next = y;
} else {
for(;;) {
int z = P2(vx[y].next);
merge(x, y);
y = z;
if(y == x) break;
}
evolution.push(x);
}
}
vint find_reachable(vint _R, vint _U, vint _V, vint _C) {
n = _R.size();
m = _U.size();
vint ans(n, 0);
for(int i = 0; i < n; ++i) {
up[i] = up2[i] = -1;
vx[i].vertices.insert(i);
vx[i].add_key(_R[i]);
}
for(int i = 0; i < m; ++i) {
int x = _U[i];
int y = _V[i];
int z = _C[i];
cout << x << " " << y << " " << z << endl;
vx[x].add_edge(y, z);
vx[y].add_edge(x, z);
}
for(int i = 0; i < n; ++i) {
evolution.push(i);
}
while(evolution.size()) {
activate(evolution.front());
evolution.pop();
}
int fp = 1e9;
for(int x : done) {
fp = min(fp, vx[x].size);
}
for(int x : done) {
if(vx[x].size == fp) {
for(int y : vx[x].vertices) {
ans[y] = 1;
}
}
}
return ans;
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// vint v = find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
// for(int i = 0; i < sz(v); ++i) {
// if(v[i]) cout << i << " ";
// }
// cout << endl;
vint v = find_reachable({0, 1, 1, 2, 2, 1, 2},
{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
for(int i = 0; i < sz(v); ++i) {
if(v[i]) cout << i << " ";
}
cout << endl;
return 0;
}
#endif
