#include "keys.h"
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 3e5 + 5;
int n, m;
int r[maxn];
int par[maxn];
int dead[maxn];
int vis[maxn];
int lst[maxn];
vector<int> todo[maxn];
vector<ii> adj[maxn];
int sz;
vector<int> ans;
int find(int x) {return (x == par[x]) ? x : par[x] = find(par[x]);}
void merge(int x, int y) {par[find(x)] = find(y);}
vector<int> seen;
void reset() {
for(int i : seen) todo[i].clear();
seen.clear();
}
void bfs(int X, int num) {
lst[X] = num;
queue<int> q;
q.push(X);
vector<int> sol;
vector<int> has(n, 0);
while(q.size()) {
int x = q.front();q.pop();
if(find(x) != X) {
merge(X, x);
lst[find(x)] = num;
reset();
return;
}
if(vis[x]) continue;
vis[x] = 1, sol.pb(x);
int key = r[x];
if(has[key] == 0) {
has[key] = 1;
for(int i : todo[key]) q.push(i);
todo[key].clear();
}
for(ii p : adj[x]) {
if(has[p.y]) q.push(p.x);
else todo[p.y].pb(p.x), seen.pb(p.y);
}
}
dead[X] = 1;
if((int)sol.size() < sz)
sz = (int)sol.size(), ans.clear();
if((int)sol.size() == sz)
for(int i : sol) ans.pb(i);
reset();
}
vector<int> find_reachable(vector<int> _r, vector<int> u, vector<int> v, vector<int> c) {
n = (int)_r.size();
m = (int)u.size();
for(int i = 0;i < n;i++) r[i] = _r[i];
for(int i = 0;i < m;i++)
adj[u[i]].pb({v[i], c[i]}), adj[v[i]].pb({u[i], c[i]});
for(int i = 0;i < n;i++) par[i] = i;
sz = n + 1;
int cnt = 1;
while(1) {
int flag = 0;
memset(vis, 0, sizeof vis);
for(int i = 0;i < n;i++)
if(find(i) == i && dead[i] == 0 && lst[i] < cnt)
bfs(i, cnt), flag = 1;
cnt++;
if(flag == 0) break;
}
vector<int> ret(n, 0);
for(int i : ans) ret[i] = 1;
return ret;
}
