#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> createFunTour(int n, int q) {
auto AskDist = [&](int x, int y) {
return hoursRequired(x, y);
};
auto AskSize = [&](int x, int y) {
return attractionsBehind(x, y);
};
int cen = 0;
for (int i = 1; i < n; i++) {
if (AskSize(cen, i) >= n / 2) {
cen = i;
}
}
vector<int> dist(n);
for (int i = 0; i < n; i++) {
if (i == cen) {
continue;
}
dist[i] = AskDist(cen, i);
}
vector<int> ch;
for (int i = 0; i < n; i++) {
if (dist[i] == 1) {
ch.push_back(i);
}
}
int k = (int) ch.size();
vector<vector<int>> ids(k);
for (int i = 0; i < n; i++) {
if (i == cen) {
continue;
}
int p = k - 1;
for (int j = 0; j + 1 < k; j++) {
if (AskDist(ch[j], i) == dist[i] - dist[ch[j]]) {
p = j;
}
}
ids[p].push_back(i);
}
for (int i = 0; i < k; i++) {
sort(ids[i].begin(), ids[i].end(), [&](int i, int j) {
return dist[i] < dist[j];
});
}
auto Good = [&]() {
int mx = 0, cnt = 0;
for (int i = 0; i < k; i++) {
mx = max(mx, (int) ids[i].size());
cnt += (int) ids[i].size();
}
return mx < cnt - mx;
};
int lst = -1;
vector<int> res;
while (Good()) {
int who = -1;
for (int i = 0; i < k; i++) {
if (i == lst) {
continue;
}
if (who == -1 || dist[ids[who].back()] < dist[ids[i].back()]) {
who = i;
}
}
res.push_back(ids[who].back());
lst = who;
}
int big = 0;
for (int i = 0; i < k; i++) {
if (ids[i].size() > ids[big].size()) {
big = i;
}
}
while (!ids[big].empty()) {
res.push_back(ids[big].back());
ids[big].pop_back();
int who = -1;
for (int i = 0; i < k; i++) {
if (i == big || ids[i].empty()) {
continue;
}
if (who == -1 || dist[ids[who].back()] < dist[ids[i].back()]) {
who = i;
}
}
if (who != -1) {
res.push_back(ids[who].back());
ids[who].pop_back();
}
}
res.push_back(cen);
return res;
}
