#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) {return a+rng()%(b-a+1);}
#define all(x) x.begin(),x.end()
struct DSU {
vector<int> p,sz;
DSU(int n) {
forn(i,n) p.pb(i), sz.pb(1);
}
int get(int u) {
return p[u]==u?u:get(p[u]);
}
void uni(int u, int v) {
u=get(u), v=get(v);
if (u==v) return;
if (sz[u]<sz[v]) swap(u,v);
p[v]=u;
sz[u]+=sz[v];
}
};
vector<int> f(vector<int>&z) {
vector<int> v;
forn(i,z.size()) if (z[i]) v.pb(i);
return v;
}
int _q=0;
int ask(vector<int>&z) {
++_q; assert(_q<=30000);
auto v=f(z);
return count_common_roads(v);
}
const int N=500;
int adj[N][N];
int b[N][N];
int br[N*N];
vector<int> find_roads(int n, vector<int>u, vector<int>v) {
int m=u.size();
if (m==n-1) {
vector<int> v; forn(i,m) v.pb(i);
return v;
}
if (n<=0) {
forn(mask,1<<m) {
vector<int> z(m,0);
forn(i,m) if ((mask>>i)&1) z[i]=1;
int cnt=0;
forn(i,m) cnt+=z[i];
if (cnt!=n-1) continue;
DSU dsu(n);
forn(i,m) if (z[i]) dsu.uni(u[i],v[i]);
if (dsu.sz[dsu.get(0)]!=n) continue;
int x=ask(z);
if (x==n-1) return f(z);
}
}
vector<int> z;
set<int> s;
forn(i,m) adj[u[i]][v[i]]=adj[v[i]][u[i]]=i;
if (n>50) exit(0);
vector<vector<int>> g(n);
forn(i,m) {
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
forn(i,n) {
DSU dsu(n);
vector<int> t;
forn(j,m) {
int x=u[j], y=v[j];
if (x==i || y==i) continue;
if (dsu.get(x)==dsu.get(y)) continue;
dsu.uni(x,y);
t.pb(j);
}
map<int,vector<int>> mp;
for(auto&v:g[i]) {
mp[dsu.get(v)].pb(adj[i][v]);
}
for(auto&it1:mp) {
int c=it1.f;
auto z=it1.s;
//cout<<"!!! "<<i<<": "<<c<<": "; for(auto&x:z) cout<<x<<' '; cout<<'\n';
auto q=t;
for(auto&it2:mp) {
if (it2.f==c) continue;
q.pb(it2.s[0]);
}
vector<pi> v;
int mx=0;
for(auto&x:z) {
q.pb(x);
int y=count_common_roads(q);
q.pop_back();
v.pb({y,x});
mx=max(mx,y);
}
for(auto&x:v) if (x.f==mx) s.insert(x.s);
}
}
for(auto&x:s) z.pb(x);
return z;
///////////////
if (m!=n*(n-1)/2) exit(0);
for (int i=1; i<n; ++i) {
vector<int> k;
for(int j=1; j<n; ++j) {
if (j==i) continue;
k.pb(adj[0][j]);
}
vector<pi> t;
int mx=0;
forn(j,n) {
if (j==i) continue;
k.pb(adj[i][j]);
int x=count_common_roads(k);
k.pop_back();
t.pb({x,j});
mx=max(mx,x);
}
for(auto&x:t) if (x.f==mx) s.insert(adj[i][x.s]);
}
for(auto&x:s) z.pb(x);
return z;
}
