#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_roads(int n, vector<int> u, vector<int> v) {\
int m = u.size();
vector<vector<pair<int, int>>> adj(n);
vector<vector<int>> mat(n, vector<int> (n, -1));
for (int i = 0; i < u.size(); i++) {
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
mat[u[i]][v[i]] = i;
mat[v[i]][u[i]] = i;
}
auto find_without_node = [&](int w) -> pair<vector<vector<int>>, vector<vector<int>>> {
int r = 0;
if (r == w) r = 1;
vector<vector<int>> spanning;
vector<vector<int>> cc;
stack<int> st; st.push(r);
vector<bool> visited(n, 0); visited[r] = 1;
do {
spanning.push_back({});
cc.push_back({});
visited[w] = 0;
while (!st.empty()) {
int a = st.top();
st.pop(); cc.back().push_back(a);
for (auto x : adj[a]) {
if (visited[x.first]) continue;
visited[x.first] = 1;
if (x.first == w) {
spanning.back().push_back(x.second+m);
continue;
}
st.push(x.first);
spanning.back().push_back(x.second);
}
}
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
visited[i] = 1;
st.push(i); break;
}
}
} while (!st.empty());
return {spanning, cc};
};
vector<int> golden;
vector<set<int>> connected(n);
for (int i = 0; i < n; i++) {
//cout << "Node " << i << endl;
auto [span, cc_nodes] = find_without_node(i);
vector<int> together;
vector<int> tocc;
for (auto y : span) {
for (auto z : y) {
if (z < m) together.push_back(z);
else tocc.push_back(z-m);
}
}
assert(tocc.size() == span.size());
for (int k = 0; k < span.size(); k++) {
vector<int> sp = together;
for (int p = 0; p < span.size(); p++) {
if (p == k) continue;
sp.push_back(tocc[p]);
}
int mean_quan = -1;
vector<int> und, mean, over;
for (auto x : cc_nodes[k]) {
if (mat[i][x] == -1) continue;
int edge = mat[i][x];
if (!connected[i].count(edge) && x < i) continue;
int to_add = edge;
if (connected[i].count(edge)) to_add = -1;
sp.push_back(edge);
int ans = count_common_roads(sp);
sp.pop_back();
if (mean_quan == -1) {
mean_quan = ans;
mean.push_back(to_add);
}
else if (ans > mean_quan) over.push_back(to_add);
else if (ans == mean_quan) mean.push_back(to_add);
else und.push_back(to_add);
}
if (over.empty()) {
while (mean.size() >= 1) {
if (mean.back() == -1) break;
//cout << "Into golden from mean: " << mean.back() << endl;
golden.push_back(mean.back());
connected[max(u[mean.back()], v[mean.back()])].insert(mean.back());
mean.pop_back();
}
} else {
while (over.size() >= 1) {
if (over.back() == -1) break;
//cout << "Into golden from over: " << over.back() << endl;
golden.push_back(over.back());
connected[max(u[over.back()], v[over.back()])].insert(over.back());
over.pop_back();
}
}
}
}
//cout << "Golden set size: " << golden.size() << endl;
assert(golden.size() == n-1);
return golden;
}
