#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 20;
namespace DSU{
int p[N];
void init(int n){
iota(p, p + n, 0);
}
int find(int u){
if(u == p[u])return u;
return p[u] = find(p[u]);
}
bool join(int u,int v){
u = find(u), v = find(v);
if(u == v)return 0;
p[u] = v ;
return 1;
}
}
bool t[N], vis[N];
map<vector<int>, int> mp;
int qry(vector<int> v){
sort(v.begin(), v.end());
if(mp.count(v))return mp[v];
return mp[v] = count_common_roads(v);
}
std::vector<int> find_roads(int n, std::vector<int> U, std::vector<int> V) {
int m = U.size();
DSU::init(n);
vector<int> ans;
for(int i = 0;i < m;i++){
if(DSU::join(U[i], V[i]))ans.push_back(i), t[i] = 1;
}
int res = qry(ans);
for(int i = 0;i < m && res < n - 1;i++){
if(!t[i] || vis[i])continue;
int mj = i;
for(int j = 0;j < m;j++){
if(t[j] || vis[j])continue;
vector<int> T;
for (auto x: ans){
if (x != i) T.push_back(x);
}
T.push_back(j);
DSU::init(n);
int cnt = 0;
for (auto u: T){
if(DSU::join(U[u],V[u]))cnt++;
}
if (cnt == n - 1){
int h = qry(T);
if (h <= res) continue;
mj = j;
t[mj] = 1;
t[i] = 0;
swap(ans, T);
res = h;
break;
}
}
vis[i] = vis[mj] = 1;
}
return ans;
}
