#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct UF {
vi e;
UF(int N) : e(N, -1) {}
int repr(int u) {
while(e[u] >= 0) u = e[u];
return u;
}
int join(int u, int v) {
u = repr(u); v = repr(v);
if(u == v) return 0;
if(e[u] > e[v]) swap(u, v);
e[u] += e[v];
e[v] = u;
return 1;
}
bool same(int u, int v) { return repr(u) == repr(v); }
void clear() { for(auto &it : e) it = -1; }
};
vi find_roads(int n, vi u, vi v) {
int m = u.size();
UF sol(n);
vector<vi> L(n);
for(int i = 0; i < m; ++i) {
L[u[i]].push_back(v[i]);
L[v[i]].push_back(u[i]);
}
vi Re;
for(int i = 0; i < n; ++i) {
sol.clear();
vector<int> Q;
for(int j = 0; j < m; ++j) {
if(u[j] != i && v[j] != i) {
if(sol.join(u[j], v[j])) {
Q.push_back(j);
}
}
}
// vector<int> Cul;
// for(int j = 0; j < m; ++j) {
// if(u[j] == i || v[j] == i) {
// int x = u[j];
// if(x == i) x = v[j];
// Cul.push_back(sol.repr(x));
// }
// }
// sort(Cul.begin(), Cul.end());
// Cul.resize(unique(Cul.begin(), Cul.end()) - Cul.begin());
// auto id = [&](int v) {
// return lower_bound(Cul.begin(), Cul.end(), v) - Cul.begin();
// };
map<int, vector<int> > M;
for(int j = 0; j < m; ++j) {
if(u[j] == i || v[j] == i) {
int x = u[j];
if(x == i) x = v[j];
M[sol.repr(x)].push_back(j);
}
}
for(auto [cul, vec] : M) {
vi QQ = Q;
for(auto [altcul, altvec] : M)
if(altcul != cul)
QQ.push_back(altvec[0]);
int rem = 0, muchie = 0;
for(auto it : vec) {
QQ.push_back(it);
int v = count_common_roads(QQ);
QQ.pop_back();
if(v > rem) {
rem = v;
muchie = it;
}
}
Re.push_back(muchie);
}
}
sort(Re.begin(), Re.end());
Re.resize(unique(Re.begin(), Re.end()) - Re.begin());
return Re;
}
