#pragma GCC optimize ("O3")
#include "simurgh.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct DSU {
int n, components;
vector<int>par;
DSU(int _n) {
n = _n;
components = n;
par.assign(n, -1);
}
int Find(int u) {
return (par[u] < 0 ? u : (par[u] = Find(par[u])));
}
bool Union(int u, int v) {
u = Find(u);
v = Find(v);
if (u != v) {
if (par[u] > par[v]) {
swap(u, v);
}
par[u] += par[v];
par[v] = u;
--components;
return true;
} else {
return false;
}
}
};
/// helperTree (construct any tree and find its edge types (royal or not))
/// findDegree (find degree for each node)
/// binarySearch (find edges connected to leaf nodes using BS)
bool cmp(array<int, 3>er1, array<int, 3>er2) {
if (er1[0] * er2[1] == er2[0] * er1[1]) {
return er1[0] > er2[0];
} else {
return er1[0] * er2[1] > er2[0] * er1[1];
}
}
vpii findHelperTree(int n, int m, vi &u, vi &v, vvi &g, vi &isRoyal) {
DSU helperTreeDSU(n);
vector<pii>helperTree;
vector<array<int, 3>>edgeRatio(n);
for (int i = 0; i < n; ++i) {
edgeRatio[i] = {size(g[i]), size(g[i]), i};
}
sort(all(edgeRatio), cmp);
for (int itr = 0; itr < n; ++itr) {
int i = edgeRatio[0][2];
DSU dsu(n);
vi r;
for (int j = 0; j < m; ++j) {
if (u[j] != i && v[j] != i && dsu.Union(u[j], v[j])) {
r.eb(j);
}
}
vi roots;
for (int j = 0; j < n; ++j) {
if (j != i && dsu.par[j] < 0) {
roots.eb(j);
}
}
vvi group(n);
for (int j : g[i]) {
int other = u[j] + v[j] - i;
group[dsu.Find(other)].eb(j);
}
for (int j = 0; j < dsu.components - 1; ++j) {
for (int k = 0; k < dsu.components - 1; ++k) {
if (k != j) {
r.eb(group[roots[k]][0]);
}
}
vi royals;
int maxVal = -1;
for (int k : group[roots[j]]) {
if (isRoyal[k] == -1) {
r.eb(k);
royals.eb(count_common_roads(r));
r.pop_back();
} else if (isRoyal[k] == 1) {
if (maxVal == -1) {
r.eb(k);
royals.eb(count_common_roads(r));
r.pop_back();
maxVal = royals.back();
} else {
royals.eb(maxVal);
}
} else {
if (maxVal == -1) {
r.eb(k);
royals.eb(count_common_roads(r));
r.pop_back();
maxVal = royals.back() + 1;
} else {
royals.eb(maxVal - 1);
}
}
}
maxVal = (*max_element(all(royals)));
for (int k = 0; k < size(group[roots[j]]); ++k) {
int id = group[roots[j]][k];
if (royals[k] == maxVal) {
isRoyal[id] = 1;
} else {
isRoyal[id] = 0;
}
if (helperTreeDSU.Union(u[id], v[id])) {
helperTree.eb(mpr(id, isRoyal[id]));
if (helperTreeDSU.components == 1) return helperTree;
}
}
for (int k = 0; k < dsu.components - 1; ++k) {
if (k != j) {
r.pop_back();
}
}
}
vector<set<int>>subTrees(n);
for (int j = 0; j < m; ++j) {
if (helperTreeDSU.Find(u[j]) != helperTreeDSU.Find(v[j])) {
subTrees[u[j]].insert(helperTreeDSU.Find(v[j]));
subTrees[v[j]].insert(helperTreeDSU.Find(u[j]));
}
}
for (int j = 0; j < n; ++j) {
edgeRatio[j] = {size(subTrees[j]), size(g[j]), j};
}
sort(all(edgeRatio), cmp);
}
}
vi findDegrees(int n, int m, vpii &helperTree, vi &u, vi &v, vvi &g) {
vi degree(n, 0);
for (int i = 0; i < n; ++i) {
DSU dsu(n);
vi r;
for (int j : g[i]) {
dsu.Union(u[j], v[j]);
r.eb(j);
}
for (auto [j, isRoyal] : helperTree) {
if (dsu.Union(u[j], v[j])) {
r.eb(j);
degree[i] -= isRoyal;
}
}
degree[i] += count_common_roads(r);
}
return degree;
}
int findRoyal(int n, vpii &helperTree, vi &edges, vi &u, vi &v) {
int low = 0, high = size(edges) - 1;
int mid;
while (low < high) {
mid = (low + high) >> 1;
DSU dsu(n);
vi r;
int royals = 0;
for (int i = low; i <= mid; ++i) {
r.eb(edges[i]);
dsu.Union(u[edges[i]], v[edges[i]]);
}
for (auto [i, isRoyal] : helperTree) {
if (dsu.Union(u[i], v[i])) {
r.eb(i);
royals -= isRoyal;
}
}
royals += count_common_roads(r);
if (royals) {
high = mid;
} else {
low = mid + 1;
}
}
return edges[low];
}
vi find_roads(int n, vi u, vi v) {
int m = size(u);
vvi g(n);
for (int i = 0; i < m; ++i) {
g[u[i]].eb(i);
g[v[i]].eb(i);
}
vi isRoyal(m, -1);
vpii helperTree = findHelperTree(n, m, u, v, g, isRoyal);
vi degree = findDegrees(n, m, helperTree, u, v, g);
queue<int>q;
for (int i = 0; i < n; ++i) {
if (degree[i] == 1) {
q.push(i);
}
}
vector<int>res;
for (int i = 1; i < n; ++i) {
int node = q.front();
q.pop();
vi edges;
int id = -1;
for (int i : g[node]) {
if (isRoyal[i] == -1) {
edges.eb(i);
} else if (isRoyal[i] == 1) {
id = i;
break;
}
}
if (id == -1) {
id = findRoyal(n, helperTree, edges, u, v);
}
for (int i : edges) {
isRoyal[i] = 0;
}
isRoyal[id] = 2;
res.eb(id);
int other = (u[id] ^ v[id] ^ node);
--degree[other];
if (degree[other] == 1) {
q.push(other);
}
}
return res;
}
