#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
using vi = vector<int>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
vvl g;
vll sz;
vpl lis;
void find_dep(ll cur, ll pr, ll d){
lis.pb({d,cur});
for(ll i:g[cur]){
if(i!=pr){
find_dep(i,cur, d+1);
}
}
}
void find_sz(ll cur, ll pr=-1){
sz[cur]=1;
for(ll i:g[cur]){
if(i!=pr){
find_sz(i,cur);
sz[cur]+=sz[i];
}
}
}
ll cen(ll cur, ll n, ll pr=-1){
for(ll i:g[cur]){
if(i!=pr){
if(sz[i]*2>n)return cen(i,n,cur);
}
}
return cur;
}
vi solve(ll cur, vvp mx, ll n){
vi ord, pri;
ll l = -1, o=-1;
while(n>0){
if(mx[0].size()>=(n+1)/2){o=0;break;}
if(mx[1].size()>=(n+1)/2){o=1;break;}
if(mx[2].size()>=(n+1)/2){o=2;break;}
ll x = -1;
for(ll i = 0; i < 3; ++i){
if(i==l || mx[i].empty())continue;
if(x==-1 || mx[i].back().f>mx[x].back().f)x=i;
}
l=x;
ord.pb(mx[x].back().s);
pri.pb(mx[x].back().f);
n--;
mx[x].pop_back();
}
if(ord.size()>1 && pri.back()<pri[pri.size()-2]){
while(n>0){
ll x=-1;
for(ll i = 0; i < 3; ++i){
if(i==o || mx[i].empty())continue;
if(x==-1 || mx[i].back().f>mx[x].back().f)x=i;
}
ord.pb(mx[x].back().s);
pri.pb(mx[x].back().f);
mx[x].pop_back();
n--;
if(n==0)break;
ord.pb(mx[o].back().s);
pri.pb(mx[o].back().f);
mx[o].pop_back();
n--;
}
}
else{
while(n>0){
ord.pb(mx[o].back().s);
pri.pb(mx[o].back().f);
mx[o].pop_back();
n--;
if(n==0)break;
ll x=-1;
for(ll i = 0; i < 3; ++i){
if(i==o || mx[i].empty())continue;
if(x==-1 || mx[i].back().f>mx[x].back().f)x=i;
}
ord.pb(mx[x].back().s);
pri.pb(mx[x].back().f);
mx[x].pop_back();
n--;
}
}
ord.pb(cur);
return ord;
}
std::vector<int> createFunTour(int n, int q) {
g = vvl(n);
sz = vll(n);
for(ll i = 1; i < n; ++i){
g[i].pb((i-1)/2);
g[(i-1)/2].pb(i);
}
// for(ll i = 0; i < n; ++i){
// for(ll j = i+1; j < n; ++j){
// if(hoursRequired(i,j)==1){
// g[i].pb(j);
// g[j].pb(i);
// }
// }
// }
find_sz(0);
ll st = cen(0,n);
vvp mx(3);
for(ll i = 0; i < g[st].size(); ++i){
lis.clear();
find_dep(g[st][i],st,1);
sort(all(lis));
mx[i]=lis;
}
vi ans = solve(st, mx, n-1);
return ans;
}
