#include <bits/stdc++.h>
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ve = vector <T>;
template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
using ull = unsigned long long;
const int oo = 1e9;
const ll OO = 1e18;
const int N = 3e5 + 10;
const int M = 5e3 + 100;
const int mod = 1e9 + 7;
const bool TEST = 0;
int n;
ve <pii> G[N];
ve <pii> NG[N];
int root[N];
int get(int u) {
return u == root[u] ? u : root[u] = get(root[u]);
}
void uni(int u, int v) {
u = get(u);
v = get(v);
root[u] = v;
}
int col[N];
int A = 1e9;
ve <int> Ans;
int WAS[N], global;
int bad[N];
ve <int> E[N];
void bfs(int st) {
WAS[st] = global;
fr(i, 0, n - 1) E[i].clear();
ve <bool> vis(n, 0), have(n, 0);
ve <int> id;
queue <int> q;
q.push(st);
while (sz(q)) {
int u = q.front();
q.pop();
if (get(u) != st) {
uni(st, u);
WAS[st] = global;
return;
}
id.pb(u);
have[col[u]] = 1;
for (auto [to, clr] : G[u]) if (!vis[to]) {
if (have[clr]) {
vis[to] = 1;
q.push(to);
} else {
E[clr].pb(to);
}
}
while (sz(E[col[u]])) {
if (!vis[E[col[u]].back()]) {
vis[E[col[u]].back()] = 1;
q.push(E[col[u]].back());
}
E[col[u]].pop_back();
}
}
bad[st] = 1;
if (sz(id) < A) {
A = sz(id);
Ans.clear();
}
if (A == sz(id)) fe(x, id) Ans.pb(x);
}
vector<int> find_reachable(vector <int> r, vector <int> u, vector <int> v, vector <int> c) {
n = sz(r);
for (int i = 0; i < n; i++) root[i] = i;
vector<int> ans(n, 0);
ve <int> C(n, 0);
for (int i = 0; i < n; i++) col[i] = r[i];
for (int i = 0; i < sz(u); i++) {
G[u[i]].pb({v[i], c[i]});
G[v[i]].pb({u[i], c[i]});
}
for (global = 1;; global++) {
bool c = 0;
for (int i = 0; i < n; i++) {
if (i == get(i) && !bad[i]) {
if (WAS[i] != global) {
bfs(i);
c = 1;
}
}
}
if (!c) break;
}
fe(x, Ans) ans[x] = 1;
return ans;
}
