#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
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(), m = u.size();
vector <vector<ar<int,2>>> adj(n);
for ( int i = 0; i < m; i++ ){
adj[u[i]].pb({v[i], c[i]});
adj[v[i]].pb({u[i], c[i]});
}
vector <vector<int>> C(n);
vector <int> fa(n), rt(n);
for ( int i = 0; i < n; i++ ){
C[i].pb(i);
fa[i] = rt[i] = i;
}
vector <int> us(n), vis(n), er, erK; // us - keys, vis - vertex
vector <vector<int>> need(n);
auto get = [&](int x){
queue <int> q;
q.push(x);
while ( !q.empty() ){
int u = q.front();
q.pop();
if ( vis[u] ) continue;
if ( us[r[u]] == 0 ){
for ( auto &v: need[r[u]] ){
q.push(v);
if ( fa[v] != fa[x] ){
return fa[v];
}
}
}
vis[u] = us[r[u]] = true;
er.pb(u);
for ( auto &[v, c]: adj[u] ){
if ( us[c] ){
q.push(v);
if ( fa[v] != fa[x] ){
return fa[v];
}
} else{
need[c].pb(v);
erK.pb(c);
}
}
}
return -1;
};
auto clear = [&](){
for ( auto &u: er ){
vis[u] = us[r[u]] = 0;
} er.clear();
for ( auto &u: erK ){
need[u].clear();
} erK.clear();
};
vector <int> K(n, 1); // random stuff
while ( true ){
vector <int> to(n, -1);
for ( int x = 0; x < n; x++ ){
if ( fa[x] != x ) continue;
to[x] = get(rt[x]);
clear();
}
//~ cout << "Components\n";
//~ for ( int i = 0; i < n; i++ ){
//~ auto &x = C[i];
//~ if ( x.empty() ) continue;
//~ for ( auto &u: x ) cout << u << ' ';
//~ cout << " -> " << rt[i] << ln;
//~ cout << ln;
//~ } cout << ln;
//~ for ( auto &x: to ) cout << x << " ";
//~ cout << "\n\n";
bool hasMerged = false;
for ( int i = 0; i < n; i++ ){
if ( i != fa[i] || to[i] == -1 ) continue;
int v = fa[to[i]];
if ( i == v ) continue;
if( C[v].empty() ) return K;
hasMerged = true;
if ( C[i].size() > C[v].size() ){
rt[i] = rt[v];
for ( auto &x: C[v] ){
C[i].pb(x);
fa[x] = i;
} C[v].clear();
} else{
for ( auto &x: C[i] ){
C[v].pb(x);
fa[x] = v;
} C[i].clear();
}
}
if ( !hasMerged ) break;
}
vector <int> ans;
int mn = n + 1;
for ( int x = 0; x < n; x++ ){
if ( x != fa[x] ) continue;
get(rt[x]);
int s = er.size();
if ( chmin(mn, s) ){
ans = er;
} else if ( s == mn ){
for ( auto &u: er ){
ans.pb(u);
}
}
clear();
}
vector <int> ret(n);
for ( auto &x: ans ) ret[x] = 1;
return ret;
}
