#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
vector<int> createFunTour(int N, int Q) {
pair<int, int> best = {N, 0};
for(int i = 0; i < N; i++){
int x = attractionsBehind(0, i);
cerr << i << ' ' << x << endl;
if (x >= (N + 1) / 2)
best = min(best, {x, i});
}
int centroid = best.second;
cerr << "centroid: " << centroid << endl;
vector<int> subtreeRoots, distToCentroid(N);
for(int i = 0; i < N; i++){
distToCentroid[i] = hoursRequired(centroid, i);
if (distToCentroid[i] == 1)
subtreeRoots.push_back(i);
}
vector<vector<pair<int, int>>> subtree(subtreeRoots.size());
for(int i = 0; i < N; i++){
if (i == centroid)
continue;
for(int j = 0; j < (int) subtreeRoots.size(); j++)
if (j == (int) subtreeRoots.size())
subtree[j].push_back({distToCentroid[i], i});
else if (hoursRequired(subtreeRoots[j], i) == distToCentroid[i] - 1)
subtree[j].push_back({distToCentroid[i], i});
}
for(auto &v : subtree)
sort(v.begin(), v.end());
for(auto v : subtree){
for(auto p : v)
cerr << p.first << ',' << p.second << ' ';
cerr << endl;
}
vector<int> answer;
int lastSubtree = -1;
for(int i = 0; i < N - 1; i++){
int rem = N - 1 - i;
pair<int, int> best{-1, -1};
for(int j = 0; j < (int) subtreeRoots.size(); j++){
if (subtree[j].empty() || j == lastSubtree)
continue;
bool ok = 1;
for(int k = 0; k < (int) subtreeRoots.size(); k++)
ok &= ((int) subtree[k].size() * 2 <= rem + 1);
if (ok)
best = max(best, {subtree[j].back().first, j});
}
lastSubtree = best.second;
cerr << "best: " << best.first << ' ' << best.second << endl;
cerr << lastSubtree << ' ' << subtree[lastSubtree].back().second << endl;
answer.push_back(subtree[lastSubtree].back().second);
subtree[lastSubtree].pop_back();
}
answer.push_back(centroid);
return answer;
}
