#include "fun.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 100100;
vector<int> g[N], ans;
vector<i2> vc[3];
int siz[N];
void build_sz(int v, int p){
siz[v] = 1;
for (int u : g[v]){
if (u == p) continue;
build_sz(u, v);
siz[v] += siz[u];
}
}
int search(int v, int p, int SZ){
for (int u : g[v]){
if (u == p) continue;
if (siz[u] > SZ / 2)
return search(u, v, SZ);
}
return v;
}
void dfs(int v, int p, int ht, int tp){
vc[tp].PB({ht, v});
for (int u : g[v]){
if (u == p) continue;
dfs(u, v, ht + 1, tp);
}
}
vector<int> createFunTour(int n, int Q) {
if (n <= 500){
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++){
int now = hoursRequired(i, j);
if (now == 1){
g[i].PB(j);
g[j].PB(i);
}
}
} else {
for (int i = 1; i < n; i++){
int j = (i - 1) / 2;
g[i].PB(j);
g[j].PB(i);
}
}
ans.clear();
build_sz(0, -1);
int cen = search(0, -1, siz[0]);
assert(sz(g[cen]) < 4);
for (int it = 0; it < sz(g[cen]); it++) {
dfs(g[cen][it], cen, 1, it);
sort(all(vc[it]));
}
int mx = -1, who = -1, tp = -1;
for (int it = 0; it < sz(g[cen]); it++)
if (sz(vc[it]) > mx){
mx = sz(vc[it]);
who = vc[it].back()[1];
tp = it;
}
vc[tp].pop_back();
ans.PB(who);
for (int itr = 2; itr < n; itr++){
int nw_mx = -1, nw = -1, wh = -1;
for (int it = 0; it < sz(g[cen]); it++){
if (it == tp || sz(vc[it]) == 0) continue;
if (sz(vc[it]) > nw_mx){
nw_mx = sz(vc[it]);
nw = vc[it].back()[1];
wh = it;
}
}
assert(wh >= 0);
vc[wh].pop_back();
ans.PB(nw);
tp = wh;
who = nw;
}
ans.PB(cen);
return ans;
}
