#include <bits/stdc++.h>
using namespace std;
#define task "task"
#define bit(x, i) ((x >> i) & 1)
// https://trap.jp/post/1224/
#define FOR1(i, a, b) for(int i = (a), _b = (b); i <= _b; i ++)
#define FOR2(i, a, b, c) for(int i = (a), _b = (b); i <= _b; i += c)
#define FORD1(i, a, b) for(int i = (a), _b = (b); i >= _b; i --)
#define FORD2(i, a, b, c) for(int i = (a), _b = (b); i >= _b; i -= c)
#define overload4(a, b, c, d, name, ...) name
#define FOR(...) overload4(__VA_ARGS__, FOR2, FOR1)(__VA_ARGS__)
#define FORD(...) overload4(__VA_ARGS__, FORD2, FORD1)(__VA_ARGS__)
#define pb emplace_back
#define pf emplace_front
#define ins emplace
#define mp make_pair
#define fi first
#define se second
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
// mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
// ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
const int N = 3e5 + 5;
const int inf = 1e9;
const int mod = 1e9 + 7;
const int base = 31;
int sz = inf;
vi r, u, v, c, ans, vis, wait[N];
vector<bool> key, sus;
vector<pii> g[N];
struct DSU{
int n, par[N];
void init(int _n){
n = _n;
FOR(i, 0, n - 1) par[i] = i;
}
int get(int u){
while(u != par[u]){ u = par[u] = par[par[u]]; }
return u;
}
bool onion(int u, int v){
u = get(u), v = get(v);
if(u != v){
par[v] = u;
vis[u] = 1;
return 1;
}
return 0;
}
} dsu;
void bfs(int s){
vi suscubus, waited, vis_key; queue<int> q;
q.ins(s);
bool check = 1;
while(q.size()){
int u = q.front(); q.pop();
if(dsu.get(u) != s){
dsu.onion(u, s);
check = 0;
break;
}
if(vis[u]) continue; vis[u] = 1;
suscubus.pb(u);
for(int v : wait[r[u]]) q.ins(v);
wait[r[u]].clear();
key[r[u]] = 1; vis_key.pb(r[u]);
for(auto [v, w] : g[u])
if(key[w]) q.ins(v);
else{
if(wait[w].empty()) waited.pb(w);
wait[w].pb(v);
}
}
for(int c : vis_key) key[c] = 0;
for(int c : waited) wait[c].clear();
if(check){
if(sz == (int)suscubus.size()) for(int c : suscubus) ans.pb(c);
if(sz > (int)suscubus.size()) ans = suscubus, sz = suscubus.size();
sus[dsu.get(s)] = 1;
for(int c : suscubus) vis[c] = 0;
}
}
vector<int> find_reachable(vector<int> _r, vector<int> _u, vector<int> _v, vector<int> _c){
r = _r, u = _u, v = _v, c = _c;
int n = r.size(), m = c.size();
sus.resize(n); key.resize(n);
dsu.init(n);
FOR(i, 0, m - 1){
g[u[i]].pb(v[i], c[i]);
g[v[i]].pb(u[i], c[i]);
}
while(1){
vis.clear(), vis.resize(n);
bool sex = 0;
FOR(i, 0, n - 1) if(!vis[i] && !sus[dsu.get(i)]) bfs(i), sex = 1;
if(!sex) break;
}
vector<int> res; res.resize(n);
for(int c : ans) res[c] = 1;
return res;
}
// void solve(){
// // vector<int> a = find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
// vector<int> a = 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 c : a) cout<<c<<" ";
// }
// signed main(){
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// if(fopen(task".inp", "r")){
// freopen(task".inp", "r", stdin);
// freopen(task".out", "w", stdout);
// }
// int nTest = 1;
// // cin>>nTest;
// while(nTest --) solve();
// cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
// return 0;
// }
