#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
#define ask count_common_roads
using namespace std;
const int N=3e4+5;
int par[N],sz[N];
bool in[N];
int getpar(int x){
if (x==par[x]) return x;
return par[x]=getpar(par[x]);
}
bool link(int x,int y){
x=getpar(x);
y=getpar(y);
if (x==y) return 0;
if (sz[x]>sz[y]) swap(x,y);
sz[y]+=sz[x];
par[x]=y;
return 1;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
int m=u.size();
for (int i=0;i<m;i++) u[i]++,v[i]++;
for (int i=1;i<=n;i++) sz[i]=1,par[i]=i;
vector<int> r;
for (int i=0;i<m;i++){
if (link(u[i],v[i])) r.pb(i),in[i]=1;
}
int ans=ask(r);
while (ans<n-1){
bool op=0;
for (int i=0;i<n-1 && !op;i++){
for (int j=0;j<m && !op;j++){
if (in[j]) continue;
vector<int> t;
for (int k=0;k<n-1;k++){
if (k==i) continue;
t.pb(r[k]);
}
t.pb(j);
for (int i=1;i<=n;i++) sz[i]=1,par[i]=i;
int tree=0;
for (auto x:t) tree+=link(u[x],v[x]);
if (tree!=n-1) continue;
int h=ask(t);
if (h<=ans) continue;
ans=h;
swap(r,t);
op=1;
break;
}
}
}
return r;
}
