#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < u.size(); i++) {
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
auto find_without_node = [&](int w) -> vector<int> {
int r = 0;
if (r == w) r = 1;
vector<int> spanning;
stack<int> st; st.push(r);
vector<bool> visited(n, 0); visited[w] = 1; visited[r] = 1;
while (!st.empty()) {
int a = st.top();
st.pop();
for (auto x : adj[a]) {
if (visited[x.first]) continue;
st.push(x.first);
spanning.push_back(x.second);
visited[x.first] = 1;
}
}
return spanning;
};
vector<int> golden;
vector<vector<int>> connected(n);
for (int i = 0; i < n; i++) {
//cout << "Node " << i << endl;
vector<int> sp = find_without_node(i);
int mean_quan = -1;
vector<int> und, mean, over;
if (!connected[i].empty()) {
sp.push_back(connected[i][0]);
mean_quan = count_common_roads(sp)-1;
sp.pop_back();
over.push_back(-1);
}
for (auto x : adj[i]) {
if (x.first < i) continue;
sp.push_back(x.second);
int ans = count_common_roads(sp);
sp.pop_back();
if (mean_quan == -1) {
mean_quan = ans;
mean.push_back(x.second);
}
else if (ans > mean_quan) over.push_back(x.second);
else if (ans == mean_quan) mean.push_back(x.second);
else und.push_back(x.second);
}
if (over.empty()) {
while (mean.size() >= 1) {
//cout << "Into golden from mean: " << mean.back() << endl;
golden.push_back(mean.back());
connected[max(u[mean.back()], v[mean.back()])].push_back(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()])].push_back(over.back());
over.pop_back();
}
}
}
//cout << "Golden set size: " << golden.size() << endl;
assert(golden.size() == n-1);
return golden;
}
