#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);
if (x >= (N + 1) / 2)
best = min(best, {x, i});
}
int centroid = best.second;
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(3);
for(int i = 0; i < N; i++){
if (i == centroid)
continue;
for(int j = 0; j < (int) subtreeRoots.size(); j++)
if (j + 1 == (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});
break;
}
}
for(auto &v : subtree)
sort(v.begin(), v.end());
vector<int> answer;
int lastSubtree = -1;
while (true){
int sum = 0, maxSz = -1, big = -1;
pair<int, int> nxt = {-1, -1};
for(int i = 0; i < 3; i++){
sum += subtree[i].size();
if (maxSz < (int) subtree[i].size()){
big = i;
maxSz = subtree[i].size();
}
if (i != lastSubtree && i < (int) subtreeRoots.size())
nxt = max(nxt, {subtree[i].back().first, i});
}
if (sum == 0)
break;
int nxtSubtree = nxt.second;
if (sum <= 2 * maxSz){
vector<int> small;
for(int i = 0; i < 3; i++)
if (i != big)
small.push_back(i);
int cur, szSmall = subtree[small[0]].size() + subtree[small[1]].size(), szBig = subtree[big].size();
if (szSmall != szBig || lastSubtree == -1){
cur = (szBig > szSmall);
} else {
assert(lastSubtree != big);
int othSmall = small[(lastSubtree == small[0])];
if (!subtree[othSmall].empty() && distToCentroid[answer.back()] < subtree[othSmall].back().first){
answer.push_back(subtree[othSmall].back().second);
subtree[othSmall].pop_back();
}
cur = 1;
}
vector<pair<int, int>> part[2];
for(int ind : small)
for(auto p : subtree[ind])
part[0].push_back(p);
sort(part[0].begin(), part[0].end());
part[1] = subtree[big];
while (!part[cur].empty()){
answer.push_back(part[cur].back().second);
part[cur].pop_back();
cur ^= 1;
}
break;
} else {
lastSubtree = nxtSubtree;
answer.push_back(subtree[lastSubtree].back().second);
subtree[lastSubtree].pop_back();
}
}
answer.push_back(centroid);
return answer;
}
