#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
#define ask count_common_roads
using namespace std;
const int N=4e4+5;
int par[N],sz[N];
bool in[N],know[N];
map<vector<int>,int> mp;
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=mp[r]=ask(r),q=1;
for (int i=0;i<m && ans<n-1;i++){
if (!in[i] || know[i]) continue;
int s=i;
for (int j=0;j<m;j++){
if (in[j] || know[j]) continue;
vector<int> t;
for (auto x:r) if (x!=i) t.pb(x);
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;
sort(t.begin(),t.end());
int h;
if (mp.find(t)==mp.end()){
assert(q<30000);
q++;
mp[t]=ask(t);
}
h=mp[t];
if (h<=ans) continue;
s=j;
in[s]=1;
in[i]=0;
swap(r,t);
ans=h;
break;
}
know[i]=1;
know[s]=1;
}
return r;
}
