#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define F first
const int MAXN=5e2+10;
const int MAXM=3e4+10;
const int MAXL=11;
const int inf=1e6;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
int n,id[MAXN][MAXN],resp[MAXN];
vector<int> g[MAXN],mst,ans;
int quantas(int l,int r,int i){
int jt=0; vector<int> v;
fall(j,1,n-1){
if(j<l || j>r){
v.pb(id[0][j]);
jt+=resp[j];
}
else v.pb(id[i][j]);
}
int ans=count_common_roads(v);
return ans-jt;
}
void dnc(int l,int r,int cur,int i){
if(!cur) return;
if(l==r){
ans.pb(id[i][l]);
return;
}
int m=(l+r)>>1;
int x=quantas(l,m,i); dnc(l,m,x,i); dnc(m+1,r,cur-x,i);
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v){
n=N;
fall(i,0,sz(u)-1) id[u[i]][v[i]]=id[v[i]][u[i]]=i;
fall(i,1,n-2) mst.pb(id[i][i+1]);
int mx=0;
fall(i,1,n-1){
mst.pb(id[0][i]);
resp[i]=count_common_roads(mst);
mst.pop_back();
mx=max(mx,resp[i]);
}
fall(i,1,n-1){
resp[i]=(resp[i]==mx);
if(resp[i]) ans.pb(id[0][i]);
}
fall(i,1,n-2){
vector<int> v(n-i-1); iota(all(v),i+1);
int cur=count_common_roads(v);
dnc(i+1,n-1,cur,i);
}
return ans;
}
