#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]));
}
if(ban.size()==1){
int u = edges[*ban.begin()][0];
int v = edges[*ban.begin()][1];
for(int i = 0;i<m;i++){
if(ban.find(i)!=ban.end())
continue;
if(edges[i][0]==u||edges[i][1]==u||edges[i][0]==v||edges[i][1]==v){
if(ds.unite(edges[i][0],edges[i][1])){
ans.push_back(i);
}
}
}
}
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);
}
}
assert(ans.size()==n-1);
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;
}
dsu eds(m);
for(int i = 0;i<m;i++){
set<int>ban;
ban.insert(i);
if(compCount(g,ban,n)>1){
ans.push_back(i);
continue;
}
set<int>temp;
vector<int>req;
req.push_back(i);
vector<int>defTree = makeTree(edges,temp,req,n);
//required edge is first edge in defTree
int a1 = count_common_roads(defTree);
defTree.erase(defTree.begin());
vector<int>newTree = makeTree(edges,ban,defTree,n);
int a2 = count_common_roads(newTree);
if(a1>a2){
ans.push_back(i);
//cout << "adding: " << i << "\n";
}
else if(a1==a2){
eds.unite(i,newTree[n-2]);
//cout << "united: " << i << " " << newTree[n-2] << "\n";
}
else if(a1<a2){
ans.push_back(newTree[n-2]);
}
}
vector<int>sets[m];
for(int i = 0;i<m;i++){
sets[eds.findRoot(i)].push_back(i);
}
set<int>searable;
for(int i : ans){
searable.insert(i);
for(int j : sets[eds.findRoot(i)]){
searable.insert(j);
}
}
ans.clear();
for(int i : searable){
ans.push_back(i);
}
if(ans.size()<n-1){
for(int i = 0;i<m;i++){
if(searable.find(i)==searable.end()){
if(sets[i].size()+ans.size()<=n-1){
for(int j : sets[i]){
ans.push_back(j);
}
}
}
}
}
assert(ans.size()==n-1);
return ans;
}
