#include "simurgh.h"
#include <algorithm>
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
struct UF{
vector<int> chef;
UF(int n){
chef.resize(n);
for(int i=0;i<n;i++)chef[i]=i;
}
int find(int a){
if(chef[a]==a)return a;
return chef[a] = find(chef[a]);
}
void fusion(int a, int b){
a = find(a);
b = find(b);
if(a!=b){
chef[a]=b;
}
}
};
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
vector<pair<int,int>> edges;
for(int i= 0;i<u.size();i++){
edges.push_back(make_pair(u[i], v[i]));
}
vector<int> re(u.size(),0);
vector<bool> done(u.size(),false);
vector<int> maxi(n,-n), mini(n,n+1);
vector<int> golden[n];
for(int node = 0 ; node < n ; node++){
UF uf(n);
vector<int> totest, spanning;
for(int i=0;i<u.size();i++){
auto e = edges[i];
if(e.first != node && e.second != node){
if(uf.find(e.first)!=uf.find(e.second)){
uf.fusion(e.first,e.second);
spanning.push_back(i);
}
}else{
if(!done[i]){
totest.push_back(i);
done[i]=true;
}
}
}
if(golden[node].size()){
totest.push_back(golden[node].back());
}
for(auto &t:totest){
vector<int> cspanning(spanning);
cspanning.push_back(t);
re[t] = count_common_roads(cspanning);
maxi[node] = max(maxi[node], re[t]);
}
for(auto &t:totest){
if(re[t]==maxi[node]){
golden[edges[t].first].push_back(t);
golden[edges[t].second].push_back(t);
}
}
}
set<int> ans;
for(int i=0;i<n;i++){
for(int &u:golden[i]){
ans.insert(u);
}
}
vector<int> out;
for(int u:ans)out.push_back(u);
return out;
}
