#include<bits/stdc++.h>
int hoursRequired(int x , int y) ;
int attractionsBehind(int x , int y) ;
std::vector<int> createFunTour(int N, int Q) {
if (N == 2)
return std::vector<int>({0, 1});
std::vector<int> siz(N);
siz[0] = N;
for (int i = 1; i < N; i++)
siz[i] = attractionsBehind(0, i);
int root = -1;
for (int i = 0; i < N; i++)
if (siz[i] >= (N + 1) / 2)
if (root == -1 || siz[root] > siz[i])
root = i;
std::vector<int> dist(N);
for (int i = 0; i < N; i++)
dist[i] = hoursRequired(root, i);
std::vector<int> sons;
std::vector<std::vector<int>> subtr;
for (int i = 0; i < N; i++)
if (dist[i] == 1)
sons.push_back(i);
subtr.resize(sons.size());
for (int i = 0; i < N; i++) {
if (i == root)
continue;
bool found = false;
for (int j = 0; !found && j < 2; j++)
if (dist[i] - dist[sons[j]] == hoursRequired(i, sons[j]))
found = true, subtr[j].push_back(i);
if (!found)
subtr[2].push_back(i);
}
auto cmp = [&dist](const int &x, const int &y) -> bool {
return dist[x] < dist[y];
};
for (auto &tr : subtr)
std::sort(tr.begin(), tr.end(), cmp);
int sum = 0;
std::pair<int, int> max(0, -1);
for (int i = 0; i < 3; i++) {
sum += subtr[i].size();
max = std::max(max, std::make_pair((int)subtr[i].size(), i));
}
if (std::abs((sum - max.first) - max.first) <= 1) {
std::vector<int> idx;
for (int i = 0; i < 3; i++)
if (i != max.second)
idx.push_back(i);
subtr[idx[0]].insert(subtr[idx[0]].end(), subtr[idx[1]].begin(), subtr[idx[1]].end());
subtr.erase(subtr.begin() + idx[1]);
sons.erase(sons.begin() + idx[1]);
}
for (auto &tr : subtr)
std::sort(tr.begin(), tr.end(), cmp);
std::vector<int> ans;
int last = -1, lastdis = 1e9;
if ((int)sons.size() == 3) {
for (int i = 0; i < 3; i++)
if (last == -1 || dist[subtr[last].back()] < dist[subtr[i].back()])
last = i;
ans.push_back(subtr[last].back());
subtr[last].pop_back();
while (true) {
int nxt = -1;
for (int i = 0; i < 3; i++)
if (i != last && (nxt == -1 || dist[subtr[nxt].back()] < dist[subtr[i].back()]))
nxt = i;
ans.push_back(subtr[nxt].back());
subtr[nxt].pop_back();
int sum = 0;
std::pair<int, int> max(0, -1);
for (int i = 0; i < 3; i++) {
sum += subtr[i].size();
max = std::max(max, std::make_pair((int)subtr[i].size(), i));
}
if (std::abs((sum - max.first) - max.first) <= 1) {
std::vector<int> idx;
for (int i = 0; i < 3; i++)
if (i != max.second)
idx.push_back(i);
if (nxt == idx[0] && dist[ans.back()] < dist[subtr[idx[1]].back()])
nxt = idx[1], ans.push_back(subtr[nxt].back()), subtr[nxt].pop_back();
else if (nxt == idx[1] && dist[ans.back()] < dist[subtr[idx[0]].back()])
nxt = idx[0], ans.push_back(subtr[nxt].back()), subtr[nxt].pop_back();
if (nxt == idx[1])
nxt = idx[0];
if (nxt >= idx[1])
--nxt;
subtr[idx[0]].insert(subtr[idx[0]].end(), subtr[idx[1]].begin(), subtr[idx[1]].end());
std::sort(subtr[idx[0]].begin(), subtr[idx[0]].end(), cmp);
subtr.erase(subtr.begin() + idx[1]);
sons.erase(sons.begin() + idx[1]);
last = nxt;
break;
}
last = nxt;
}
} else {
last = (dist[subtr[0].back()] > dist[subtr[1].back()]) ? 0 : 1;
ans.push_back(subtr[last].back());
subtr[last].pop_back();
}
while (true) {
int nxt = last ^ 1;
ans.push_back(subtr[nxt].back());
subtr[nxt].pop_back();
if (subtr[last].empty() && (int)subtr[nxt].size() == 1) {
ans.push_back(subtr[nxt].back());
ans.push_back(root);
return ans;
}
if (ans.size() == N - 1) {
ans.push_back(root);
return ans;
}
last ^= 1;
}
}
