#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n, seen[500], usede[125000], in_set[500], royal[125000], cnt;
vector<pii> adj[500];
vector<int> u,v;
struct DSU {
vector<int> dsu;
DSU (int n) {
dsu.resize(n);
iota(dsu.begin(), dsu.end(), 0);
}
int f(int x) {return dsu[x] == x ? x : dsu[x] = f(dsu[x]);}
bool merge(int a, int b) {
a = f(a), b = f(b);
if (a != b) {
dsu[b] = a;
return 1;
}
return 0;
}
};
void dfs(int u, int ma, int ex, vector<int> &r, DSU &dsu) {
seen[u] = cnt;
for (pii v: adj[u]) {
if (u == ma && dsu.f(v.first) == ex) continue;
if (dsu.f(u) == ex && v.first == ma) continue;
if (seen[v.first] != cnt) {
r.push_back(v.second);
dfs(v.first, ma, ex, r, dsu);
}
}
}
void dfs2(int u, vector<int> &r) {
seen[u] = cnt;
for (pii v: adj[u]) {
if (seen[v.first] != cnt) {
if (!in_set[v.first]) r.push_back(v.second);
dfs2(v.first, r);
}
}
}
int query(int offset, vector<int> &edges, vector<int> &span) {
vector<int> res = edges;
DSU dsu(n);
for (int e: edges) {
dsu.merge(u[e], v[e]);
}
for (int e: span) {
if (dsu.merge(u[e], v[e])) {
res.push_back(e);
offset += royal[e];
}
}
return count_common_roads(res) - offset;
}
void dnc(int cnt, int offset, vector<int> &edges, vector<int> &span) {
if (cnt == 0) return;
if (cnt == edges.size()) {
for (int e: edges) royal[e] = 1;
return;
}
int m = edges.size() / 2;
vector<int> lft, rht;
for (int e: edges) {
(lft.size() < m ? lft : rht).push_back(e);
}
int res = query(offset, lft, span);
dnc(res, offset, lft, span);
dnc(cnt-res, offset, rht, span);
}
std::vector<int> find_roads(int _n, std::vector<int> _u, std::vector<int> _v) {
n = _n;
u = _u;
v = _v;
vector<int> ans, stk{0}, span;
in_set[0] = 1;
for (int i = 0; i < u.size(); ++i) {
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
while (stk.size()) {
int i = stk.back(); stk.pop_back();
vector<int> nxt;
DSU dsu(n);
for (int j = 0; j < u.size(); ++j) {
if (u[j] != i && v[j] != i) dsu.merge(u[j], v[j]);
}
vector<vector<pii>> es(n);
for (pii e: adj[i]) es[dsu.f(e.first)].push_back(e);
vector<int> vals = dsu.dsu;
sort(vals.begin(), vals.end());
vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
for (int ex: vals) if (ex != i) {
vector<int> r;
cnt++;
for (int j = 0; j < n; ++j) if (j != i && seen[j] != cnt) {
dfs(j, i, ex, r, dsu);
}
bool seen_royal = 0;
vector<pii> res;
for (pii e: es[ex]) {
if (!usede[e.second] || (!seen_royal && royal[e.second])) {
if (!in_set[e.first]) {
in_set[e.first] = 1;
nxt.push_back(e.first);
span.push_back(e.second);
}
usede[e.second] = 1;
if (royal[e.second]) seen_royal = 1;
r.push_back(e.second);
res.push_back({count_common_roads(r), e.second});
r.pop_back();
}
}
sort(res.begin(), res.end());
int bst = res.back().first;
while (res.size() && res.back().first == bst) {
if (!royal[res.back().second]) {
royal[res.back().second] = 1;
}
res.pop_back();
}
}
vector<int> total_span = span;
cnt++;
dfs2(0, total_span);
int span_rcnt = 0;
for (int e: span) span_rcnt += royal[e];
for (int nx: nxt) {
vector<int> edges;
stk.push_back(nx);
for (pii e: adj[nx]) if (in_set[e.first] && !usede[e.second]) {
edges.push_back(e.second);
usede[e.second] = 1;
}
int offset = count_common_roads(total_span) - span_rcnt;
dnc(query(offset, edges, total_span), offset, edges, total_span);
}
}
for (int i = 0; i < u.size(); ++i) if (royal[i]) ans.push_back(i);
return ans;
}
