#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=505;
int vs[nx], edg[nx][nx], deg[nx], vl[nx][nx], mx, used[nx];
vector<int> qrs, tmp, res;
std::vector<int> find_roads(int n, std::vector<int> _u, std::vector<int> _v) {
for (int i=0; i<_u.size(); i++) edg[_u[i]][_v[i]]=edg[_v[i]][_u[i]]=i;
for (int i=0; i<n; i++) for (int j=0; j<n; j++) vl[i][j]=-1;
for (int i=1; i<n; i++)
{
qrs.clear();
for (int j=0; j<n; j++) if (j!=i) qrs.push_back(edg[i][j]);
deg[i]=count_common_roads(qrs);
}
qrs.clear();
for (int i=1; i<n-1; i++) qrs.push_back(edg[i][i+1]);
tmp.resize(n);
for (int i=1; i<n; i++)
{
qrs.push_back(edg[0][i]);
tmp[i]=count_common_roads(qrs);
qrs.pop_back();
mx=max(mx, tmp[i]);
}
for (int i=1; i<n; i++)
{
if (tmp[i]==mx) deg[i]--, vl[0][i]=vl[i][0]=1;
else vl[0][i]=vl[i][0]=0;
}
for (int i=1; i<n; i++)
{
//cout<<"deg "<<i<<' '<<deg[i]<<'\n';
while (deg[i]>0)
{
vector<int> bs;
for (int j=0; j<n; j++) if (j!=i&&vl[i][j]==-1) bs.push_back(j);
int l=0, r=bs.size()-1;
while (l<r)
{
int md=(l+r)/2, expected=0;
for (int j=0; j<n; j++) used[j]=0;
qrs.clear();
for (int j=l; j<=md; j++) qrs.push_back(edg[i][bs[j]]), used[i]=used[bs[j]]=1;
if (!used[0]) used[0]=1, expected+=vl[i][0], qrs.push_back(edg[i][0]);
for (int j=0; j<n; j++) if (!used[j]) qrs.push_back(edg[0][j]), expected+=vl[0][j];
if (count_common_roads(qrs)==expected)
{
for (int j=l; j<=md; j++) vl[i][bs[j]]=vl[bs[j]][i]=0;
l=md+1;
}
else r=md;
}
vl[i][bs[l]]=vl[bs[l]][i]=1;
//cout<<"edge "<<i<<' '<<bs[l]<<'\n';
deg[i]--;
deg[bs[l]]--;
}
}
for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) if (vl[i][j]==1) res.push_back(edg[i][j]);
return res;
}
