#include "simurgh.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxN = 510, maxE = maxN * maxN / 2;
int cmp[maxN], from[maxE], to[maxE], r, n;
bool mark[maxN], good[maxE];
bool flag[maxN];
vector <int> adj[maxN], ans, tree;
vector <int> edge[maxN];
void DFS(int v, int id)
{
mark[v] = true;
cmp[v] = id;
for (auto i : adj[v])
{
int u = from[i] + to[i] - v;
if(u == r || mark[u]) continue ;
tree.pb(i);
DFS(u, id);
}
}
void solve(int v)
{
memset(mark, 0, sizeof mark);
r = v;
int sz = 0;
tree.clear();
for (int i=0; i<n; i++)
{
if(i == v || mark[i]) continue ;
DFS(i, sz);
sz ++;
}
memset(flag, 0, sizeof flag);
for (auto i : adj[v])
{
int u = from[i] + to[i] - v;
if(good[i] && !flag[cmp[u]]) edge[cmp[u]].pb(i), flag[cmp[u]] = true;
else if(!good[i]) edge[cmp[u]].pb(i);
}
//cout << " FIRST " << v << " --> " << sz << endl;
//for (auto x : tree) cout << x << ' '; cout << endl;
for (int i=0; i<sz; i++)
tree.pb(edge[i][0]);
int last_ans = -1;
for (int i=0; i<sz; i++)
{
int td = edge[i].size(), mx = -1;
vector <int> tmp;
if(last_ans != -1) tmp.pb(last_ans), mx = last_ans;
else
{
int r = count_common_roads(tree);
tmp.pb(r);
mx = r;
last_ans = r;
}
for (int j=1; j<td; j++)
{
tree[n - sz - 1 + i] = edge[i][j];
int r = count_common_roads(tree);
tmp.pb(r);
mx = max(mx, r);
last_ans = r;
}
for (int j=0; j<td; j++) {
if(tmp[j] == mx) ans.pb(edge[i][j]), good[edge[i][j]] = true;
}
}
//cout << ans.size() << endl;
for (int i=0; i<sz; i++) edge[i].clear();
}
std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
int m = u.size(); n = _n;
for (int i=0; i<m; i++)
{
from[i] = u[i];
to[i] = v[i];
adj[u[i]].pb(i);
adj[v[i]].pb(i);
}
for (int i=0; i<n; i++) solve(i);
sort(ans.begin(), ans.end());
ans.resize(unique(ans.begin(), ans.end()) - ans.begin());
return ans;
}
