#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;
set<int> elms[N];
int siz[N], glob, mx;
bool mrk[N];
void dfs(int v, int p, int len){
if (mx < len){
mx = len;
glob = v;
}
for (int u : g[v]){
if (u == p || mrk[u]) continue;
dfs(u, v, len + 1);
}
}
void add(int v){
for (int u : g[v])
add(u);
int mem = v;
while (1){
elms[v].insert(mem);
if (v == 0) break;
v = ((v - 1) >> 1);
}
}
void delt(int v){
int mem = v;
while (1){
elms[v].erase(mem);
if (v == 0) break;
v = ((v - 1) >> 1);
}
}
int get_len(int v, int p){
int len = 0;
while (v != p){
len++;
v = ((v - 1) >> 1);
}
return len;
}
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
{
// if (n < 10) while (1) {}
for (int i = 1; i < n; i++){
int j = (i - 1) / 2;
// g[i].PB(j);
g[j].PB(i);
}
add(0);
int rem = n, now = n - 1;
while (1){
ans.PB(now);
rem--;
mrk[now] = 1;
delt(now);
if (rem == 0) break;
int mx = -1, who = -1;
int cur = now, len = 0, pre = -1;
if (sz(elms[cur]) > 0){
int vl = (*(--elms[cur].end()));
int upd = len + get_len(vl, cur);
if (upd > mx){
mx = upd;
who = vl;
}
}
while (1){
if (cur == 0) break;
pre = cur;
cur = ((cur - 1) >> 1);
len++;
if (!mrk[cur]) {
if (mx < len){
mx = len;
who = cur;
}
}
for (int u : g[cur]){
if (u == pre) continue;
if (mrk[u] || sz(elms[u]) == 0) continue;
int vl = (*(--elms[u].end()));
int upd = len + get_len(vl, cur);
if (upd > mx){
mx = upd;
who = vl;
}
}
}
assert(who >= 0);
now = who;
}
return ans;
}
ans.clear();
mx = -1;
dfs(0, -1, 0);
for (int it = 0; it < n; it++){
ans.PB(glob);
mrk[glob] = 1;
mx = -1;
dfs(glob, -1, 0);
}
return ans;
}
