#include "fun.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#define clog std::cerr
#else
#define clog if (0) std::cerr
#endif
std::vector<int> createFunTour(int N, int Q) {
std::vector<std::pair<int, int>> subtree_size(N);
subtree_size[0] = {N, 0};
for (int i = 1; i < N; i++) {
subtree_size[i] = {attractionsBehind(0, i), i};
}
std::sort(subtree_size.begin(), subtree_size.end());
int centroid = -1;
for (centroid = 0; centroid < N; centroid++) {
if (subtree_size[centroid].first >= (N + 1) / 2) {
centroid = subtree_size[centroid].second;
break;
}
}
clog << centroid << std::endl;
assert(centroid != -1);
std::vector<std::pair<int, int>> dist(N);
std::vector<int> d(N);
for (int i = 0; i < N; i++) {
if (i == centroid) {
dist[i] = {0, i};
} else {
dist[i] = {hoursRequired(centroid, i), i};
}
d[i] = dist[i].first;
}
std::sort(dist.begin(), dist.end());
std::vector<int> adj;
for (int i = 1; i < N; i++) {
if (dist[i].first == 1) {
adj.push_back(dist[i].second);
}
}
// now we know that
std::vector<std::vector<int>> nodes(adj.size());
std::vector<int> belong(N, -1);
for (int i = 0; i + 1 < (int) adj.size(); i++) {
int u = adj[i];
for (int j = 0; j < N; j++) {
if (j == u) {
belong[j] = i;
continue;
}
if (j == centroid) continue;
int v = hoursRequired(u, j);
if (v + 1 == d[j]) {
belong[j] = i;
}
}
}
for (int j = 0; j < N; j++) {
if (j == centroid) continue;
if (belong[j] == -1) {
belong[j] = adj.size() - 1;
}
nodes[belong[j]].emplace_back(j);
}
int sz = nodes.size();
std::sort(nodes.begin(), nodes.end(), [&](const std::vector<int>& a, const std::vector<int>& b) {
return a.size() > b.size();
});
if (sz == 3 && nodes[0].size() == nodes[1].size() + nodes[2].size()) {
nodes[1].insert(nodes[1].end(), nodes[2].begin(), nodes[2].end());
nodes.pop_back();
sz--;
}
for (int i = 0; i < sz; i++) {
for (int u : nodes[i]) {
belong[u] = i;
}
std::sort(nodes[i].begin(), nodes[i].end(), [&](int x, int y) { return d[x] < d[y]; });
}
auto orig = nodes;
std::vector<int> tour = {nodes[0].back()};
for (int i = 1; i < sz; i++) {
if (d[nodes[i].back()] > d[tour[0]]) {
tour[0] = nodes[i].back();
}
}
nodes[belong[tour[0]]].pop_back();
auto merge = [&](int i, int j) {
int rem = 0 ^ 1 ^ 2 ^ i ^ j;
auto lmao = nodes[rem];
std::vector<int> ok = nodes[i];
ok.insert(ok.end(), nodes[j].begin(), nodes[j].end());
nodes.clear();
nodes.push_back(ok);
nodes.push_back(lmao);
for (int i : nodes[0]) belong[i] = 0;
for (int j : nodes[1]) belong[j] = 1;
sz = 2;
for (int i = 0; i < sz; i++) {
std::sort(nodes[i].begin(), nodes[i].end(), [&](int x, int y) { return d[x] < d[y]; });
}
};
for (int i = 1; i < N - 1; i++) {
int v = belong[tour.back()];
if (sz == 2) {
v ^= 1;
tour.push_back(nodes[v].back());
nodes[v].pop_back();
continue;
}
std::vector<int> rem(3);
for (int i = 0; i < 3; i++) {
rem[i] = i;
}
rem.erase(rem.begin() + v);
if (nodes[v].size() + nodes[rem[0]].size() == nodes[rem[1]].size()) {
merge(v, rem[0]);
v = 1;
} else if (nodes[v].size() + nodes[rem[1]].size() == nodes[rem[0]].size()) {
merge(v, rem[1]);
v = 1;
} else {
v = rem[(d[nodes[rem[0]].back()] < d[nodes[rem[1]].back()])];
}
tour.push_back(nodes[v].back());
nodes[v].pop_back();
}
tour.push_back(centroid);
return tour;
}
