#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
int n;
vector<int> adj[N];
vector<int> res;
int deg[N];
bool ch[N];
void dfs(int v, vector<int>& node, int p = -1) {
node.push_back(v);
for (auto& x : adj[v]) {
if (x == p || ch[x]) continue;
dfs(x, node, v);
}
}
void dnc(int v, int lv = 0) {
if (ch[v]) return;
vector<int> l, r;
bool __ = 0;
for (auto& x : adj[v]) {
if (ch[x]) continue;
if (!__) dfs(x, l, v), __ = 1;
else dfs(x, r, v);
}
sort(l.rbegin(), l.rend()), sort(r.rbegin(), r.rend());
int sz = r.size();
if (l.size() == r.size()) {
for (int i = 0;i < sz;i++) {
res.push_back(l[i]);
res.push_back(r[i]);
ch[l[i]] = 1;
ch[r[i]] = 1;
}
}
else {
for (int i = 0;i < sz;i++) {
res.push_back(l[i]);
res.push_back(r[i]);
ch[l[i]] = ch[r[i]] = 1;
}
res.push_back(l[sz]);
ch[l[sz]] = 1;
}
res.push_back(v);
ch[v] = 1;
dnc(l.back());
}
vector<int> createFunTour(int _N, int Q) {
n = _N;
if (n <= 500) {
vector<bool> ch(n, false);
vector<vector<int>> dis(n, vector<int>(n, 0));
for (int i = 0;i < n;i++) {
for (int j = i + 1;j < n;j++) {
dis[i][j] = dis[j][i] = hoursRequired(i, j);
}
}
int mx = 0, idx = 0;
for (int i = 0;i < n;i++) {
if (dis[0][i] > mx) {
mx = dis[0][i];
idx = i;
}
}
vector<int> res;
res.push_back(idx);
ch[idx] = 1;
for (int i = 1;i < n;i++) {
int mx = 0, idx = 0;
for (int j = 0;j < n;j++) {
if (ch[j]) continue;
if (dis[res.back()][j] > mx) {
mx = dis[res.back()][j];
idx = j;
}
}
ch[idx] = 1;
res.push_back(idx);
}
return res;
}
for (int i = 1;i < n;i++) {
adj[i].push_back((i - 1) / 2);
adj[(i - 1) / 2].push_back(i);
}
dnc(0);
return res;
}
