#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
class UnionFind {
public:
vector<int>par;
void init(int sz) { par.resize(sz, -1); }
int root(int pos) {
if (par[pos] == -1) return pos;
par[pos] = root(par[pos]);
return par[pos];
}
void unite(int u, int v) { u = root(u); v = root(v); par[u] = v; }
};
int N, M, A[1 << 18], B[1 << 18], id[509][509], col[509], ming[509], represent[509], cnts; bool forced[509];
vector<int>G[509], ans; int rr[509][509];
vector<pair<int, int>> R[509];
void dfs(int root, int pos) {
if (col[pos] >= 1) return;
col[pos] = cnts;
if (id[root][pos] >= 0) {
represent[cnts] = pos;
if (root > pos && rr[root][pos] == 1) ming[cnts] = pos;
}
for (int t : G[pos]) dfs(root, t);
}
void solve(int pos) {
UnionFind UF; UF.init(N); vector<int>v;
for (int i = 0; i < N; i++) { G[i].clear(); R[i].clear(); col[i] = 0; ming[i] = -1; represent[i] = 0; cnts = 0; forced[i] = false; }
for (int i = 0; i < M; i++) {
if (A[i] == pos || B[i] == pos) continue;
if (UF.root(A[i]) == UF.root(B[i])) continue;
UF.unite(A[i], B[i]); v.push_back(i);
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
for (int i = 0; i < N; i++) {
if (i == pos || col[i] >= 1) continue;
cnts++; dfs(pos, i);
}
for (int i = 1; i <= cnts; i++) { if (ming[i] >= 0) forced[ming[i]] = true; }
for (int i = 0; i < N; i++) {
if (id[pos][i] == -1) continue;
if (pos > i && forced[i] == false) continue;
vector<int>vec = v;
for (int j = 1; j <= cnts; j++) { if (j == col[i]) continue; vec.push_back(id[pos][represent[j]]); }
vec.push_back(id[pos][i]);
int E = count_common_roads(vec);
R[col[i]].push_back(make_pair(E, i));
}
for (int i = 1; i <= cnts; i++) {
sort(R[i].begin(), R[i].end());
reverse(R[i].begin(), R[i].end());
for (int j = 0; j < R[i].size(); j++) { if (R[i][j].first == R[i][0].first) { ans.push_back(id[pos][R[i][j].second]); rr[pos][R[i][j].second] = 1; rr[R[i][j].second][pos] = 1; } }
}
}
void find_array(int pos) {
int cx = 0, cnt = 0;
while (true) {
int cl = cx, cr = N, cm, minx = (1 << 30);
for (int i = 0; i < 11; i++) {
cm = (cl + cr) / 2;
vector<int> vec; for (int j = 0; j < N; j++) { if (j == pos) continue; if (j <= cm) vec.push_back(id[pos][j]); else vec.push_back(id[0][j]); }
int E = count_common_roads(vec);
for (int j = cm + 1; j < N; j++) { if (j == pos) continue; E -= rr[0][j]; }
//cout << "pos = " << pos << ", cm = " << cm << ", E = " << E << ", cnt = " << cnt << endl;
if (E >= cnt + 1) { minx = min(minx, cm); cr = cm; }
else { cl = cm; }
}
if (minx == (1 << 30)) break;
ans.push_back(id[pos][minx]); //cout << "# " << pos << " " << minx << endl;
cx = minx + 1; cnt++;
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
N = n; M = u.size();
for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) id[i][j] = -1; }
for (int i = 0; i < M; i++) { id[u[i]][v[i]] = i; id[v[i]][u[i]] = i; A[i] = u[i]; B[i] = v[i]; }
if (N * (N - 1) / 2 != M) {
for (int i = 0; i < N; i++) solve(i);
}
else {
solve(0);
for (int j = 1; j < N; j++) find_array(j);
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
//cout << "#answer = "; for (int i = 0; i < ans.size(); i++) cout << ans[i] << ", "; cout << endl;
return ans;
}
