#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 5e3 + 5;
int n, m;
arr<vec<int>, N> adj;
map<int, pii> edg;
map<pii, int> id;
vec<int> spn, bck;
arr<bool, N> vs;
arr<int, N> pr, dpt;
void dfs(int u = 0) {
vs[u] = true;
for (int v : adj[u]) {
if (vs[v]) {
if (v == pr[u]) continue;
if (dpt[v] < dpt[u]) bck.push_back(id[{u, v}]);
} else {
pr[v] = u, dpt[v] = dpt[u] + 1;
spn.push_back(id[{u, v}]);
dfs(v);
}
}
}
map<int, vec<int>> ovr;
void ovr_cmp() {
for (int i : bck) {
int u = edg[i].fir, v = edg[i].sec;
if (dpt[u] > dpt[v]) swap(u, v);
while (v != u) {
ovr[id[{v, pr[v]}]].push_back(i);
v = pr[v];
}
}
}
int qry(vec<int> x) {
vec<sig> y;
y.insert(y.end(), x.begin(), x.end());
return count_common_roads(y);
}
map<int, int> on;
void on_cmp() {
for (int i = 0; i < m; i++) on[i] = -1;
for (int i : spn) {
vec<int> bs = spn;
bs.erase(find(bs.begin(), bs.end(), i));
vec<int> lst = {i};
bool flg = false;
for (int j : ovr[i]) {
if (!flg && on[j] == 1) lst.push_back(j), flg = true;
if (on[j] == -1) lst.push_back(j);
}
int mx = -1;
map<int, int> rsp;
for (int j : lst) {
bs.push_back(j);
rsp[j] = qry(bs);
mx = max(mx, rsp[j]);
bs.pop_back();
}
for (int j : lst) {
if (rsp[j] == mx) on[j] = 1;
else on[j] = 0;
}
// cout << i << ": " << mx.fir << " " << mx.sec << endl;
// for (int j : lst) cout << j << " ";
// cout << endl;
}
}
vec<sig> find_roads(sig _n, vec<sig> _u, vec<sig> _v) {
n = _n, m = _u.size();
for (int i = 0; i < m; i++) {
adj[_u[i]].push_back(_v[i]), adj[_v[i]].push_back(_u[i]);
edg[i] = {_u[i], _v[i]};
id[{_u[i], _v[i]}] = id[{_v[i], _u[i]}] = i;
}
dfs();
ovr_cmp();
on_cmp();
// for (int x : spn) cout << x << " ";
// cout << endl;
// for (int x : bck) cout << x << " ";
// cout << endl;
// for (pair<int, vec<int>> x : ovr) {
// cout << x.fir << ": ";
// for (int y : x.sec) cout << y << " ";
// cout << endl;
// }
// for (int i = 0; i < m; i++) {
// cout << i << ": " << on[i] << endl;
// }
vec<sig> ans;
for (int i = 0; i < m; i++)
if (on[i] == 1) ans.push_back(i);
assert(ans.size() == n - 1);
return ans;
}
