#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
vector<int>root;
vector<int>siz;
dsu(int n){
root=vector<int>(n);
iota(root.begin(),root.end(),0);
siz=vector<int>(n,1);
}
bool unite(int x, int y){
x=findRoot(x);
y=findRoot(y);
if(x==y)
return 0;
if(siz[x]<siz[y]){
swap(x,y);
}
siz[x]+=siz[y];
root[y]=x;
return 1;
}
int findRoot(int x){
if(x==root[x])
return x;
return root[x]=findRoot(root[x]);
}
};
void dfs(int st, vector<array<int,2>>(&g)[], set<int>(&ban), bool vis[]){
vis[st]=1;
for(array<int,2>e:g[st]){
if(vis[e[0]]||ban.find(e[1])!=ban.end())
continue;
dfs(e[0],g,ban,vis);
}
}
int compCount(vector<array<int,2>>(&g)[], set<int>(&ban), int n){
int ans = 0;
bool vis[n];
fill(vis,vis+n,0);
for(int i = 0;i<n;i++){
if(!vis[i]){
ans++;
dfs(i,g,ban,vis);
}
}
return ans;
}
vector<int> makeTree(vector<array<int,2>>edges, set<int>(&ban), vector<int>req, int n){
//assuming req is without cycle
int m = edges.size();
dsu ds(n);
vector<int>ans;
for(int i : req){
ans.push_back(i);
assert(ds.unite(edges[i][0],edges[i][1]));
}
for(int i = 0;i<m;i++){
if(ban.find(i)==ban.end()&&ds.unite(edges[i][0],edges[i][1])){
ans.push_back(i);
}
}
return ans;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
vector<int>ans;
int m = u.size();
//each edge: {v,edge_index}
vector<array<int,2>>g[n];
vector<array<int,2>>edges(m);
for(int i = 0;i<m;i++){
int a = u[i];
int b = v[i];
g[a].push_back({b,i});
g[b].push_back({a,i});
edges[i][0]=a;
edges[i][1]=b;
}
for(int i = 0;i<(1<<m);i++){
if(__builtin_popcount(i)!=n-1){
continue;
}
dsu ds(n);
vector<int>curr;
for(int j = 0;j<m;j++){
if(i&(1<<j)){
if(!ds.unite(edges[j][0],edges[j][1])){
goto bad;
}
curr.push_back(j);
}
}
if(count_common_roads(curr)==n-1){
return curr;
}
bad:
continue;
}
return ans;
}
