#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
void setDsu(vector<int> &dsu, vector<int> &sz) {
int n = dsu.size();
for (int i = 0; i < n; ++i) dsu[i] = i, sz[i] = 1;
}
int findHead(vector<int> &dsu, int node) {
if (node == dsu[node]) return node;
return dsu[node] = findHead(dsu, dsu[node]);
}
bool merge(vector<int> &dsu, vector<int> &sz, int a, int b) {
a = findHead(dsu, a);
b = findHead(dsu, b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
dsu[b] = a;
sz[a] += b;
return true;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
if (n == 2) return {0};
int m = u.size();
vector<vector<pair<int, int>>> adjacency(n);
vector<vector<pair<int, int>>> adjacencyMatrix(n, vector<pair<int, int>>(n, {0, -1}));
for (int i = 0; i < m; ++i) {
adjacency[u[i]].emplace_back(v[i], i);
adjacency[v[i]].emplace_back(u[i], i);
adjacencyMatrix[u[i]][v[i]] = {1, i};
adjacencyMatrix[v[i]][u[i]] = {1, i};
}
vector<pair<int, int>> t(n - 1);
for (int i = 0; i < n - 1; ++i) t[i] = {i, i + 1};
vector<int> res;
vector<int> tWeight(n - 1, 0), dsu(n), sz(n);
vector<int> sub(n, 0);
for (int i = 0; i < n - 1; ++i) {
vector<pair<int, int>> curCycle = {t[i]};
int other = 0;
if (t[i].first == 0 || t[i].second == 0) {
other = 1;
if (t[i].first == 1 || t[i].second == 1) other = 2;
}
curCycle.emplace_back(t[i].first, other);
curCycle.emplace_back(t[i].second, other);
vector<int> scores;
for (int j = 0; j < 3; ++j) {
vector<int> r;
setDsu(dsu, sz);
for (int k = 0; k < 3; ++k) {
if (j == k) continue;
assert(merge(dsu, sz, curCycle[k].first, curCycle[k].second));
r.push_back(adjacencyMatrix[curCycle[k].first][curCycle[k].second].second);
}
for (auto &[a, b] : t) {
if (merge(dsu, sz, a, b)) r.push_back(adjacencyMatrix[a][b].second);
}
// assert(r.size() == n - 1);
scores.push_back(count_common_roads(r));
}
int least = scores[0], most = scores[0];
for (int &j : scores) least = min(least, j), most = max(most, j);
if (scores[0] != most) {
tWeight[i] = 1;
res.push_back(adjacencyMatrix[t[i].first][t[i].second].second);
++sub[t[i].first];
++sub[t[i].second];
}
}
vector<int> nodeWeights(n, -1);
for (int node = 0; node < n; ++node) {
setDsu(dsu, sz);
vector<int> r;
for (auto &[adjacent, index] : adjacency[node]) {
// assert(merge(dsu, sz, node, adjacent));
r.push_back(index);
}
int base = 0;
for (int i = 0; i < n - 1; ++i) {
if (merge(dsu, sz, t[i].first, t[i].second)) {
r.push_back(adjacencyMatrix[t[i].first][t[i].second].second);
base += tWeight[i];
}
}
// assert(r.size() == n - 1);
nodeWeights[node] = count_common_roads(r) - base;
}
while (res.size() != n - 1) {
for (int node = 0; node < n; ++node) {
if (nodeWeights[node] - sub[node] != 1) continue;
int low = 0, high = adjacency[node].size() - sub[node];
while (low < high - 1) {
int mid = (low + high) / 2;
setDsu(dsu, sz);
vector<int> r;
int shift = 0;
for (int i = 0; i < mid; ++i) {
if (nodeWeights[adjacency[node][i + shift].first] == sub[adjacency[node][i + shift].first]) {
--i; ++shift;
continue;
}
// assert(merge(dsu, sz, node, adjacency[node][i + shift].first));
r.push_back(adjacency[node][i + shift].second);
}
int base = 0;
for (int i = 0; i < n - 1; ++i) {
if (merge(dsu, sz, t[i].first, t[i].second)) {
r.push_back(adjacencyMatrix[t[i].first][t[i].second].second);
base += tWeight[i];
}
}
// assert(r.size() == n - 1);
if (count_common_roads(r) - base) high = mid;
else low = mid;
}
int shift = 0;
for (int i = 0; i <= low; ++i) {
if (nodeWeights[adjacency[node][i + shift].first] == sub[adjacency[node][i + shift].first]) {
--i; ++shift;
continue;
}
}
shift += low;
res.push_back(adjacency[node][shift].second);
++sub[node];
++sub[adjacency[node][shift].first];
}
}
return res;
}
