#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 +5;
vector<int> tr[M];
int dist[M];
void cnt(int node,int par){
for(auto i:tr[node]){
if(i != par){
dist[i] = dist[node]+1;
cnt(i,node);
}
}
}
vector<int> nxt[M],nxt2[M];
vector<int> createFunTour(int N, int Q) {
/*
int H = hoursRequired(0, N - 1);
int A = attractionsBehind(0, N - 1);
*/
for(int i=1;i<N;i++){
int s = (i-1)/2;
tr[s].push_back(i);
tr[i].push_back(s);
}
cnt(0,-1);
int st = 0,mx = 0;
for(int i=1;i<N;i++){
int q = dist[i];
if(q > mx){
st = i;
mx = q;
}
}
dist[st] = 0;
cnt(st,-1);
for(int i=0;i<N;i++){
nxt[dist[i]].push_back(i);
}
int en = 0;
mx = 0;
for(int i=1;i<N;i++){
int q = dist[i];
if(q > mx){
en = i;
mx = q;
}
}
dist[en] = 0;
cnt(en,-1);
for(int i=0;i<N;i++){
nxt2[dist[i]].push_back(i);
}
vector<int> f,s;
for(int i=N-1;i>=0;i--){
sort(nxt[i].rbegin(),nxt[i].rend());
for(auto x:nxt[i]){
f.push_back(x);
}
sort(nxt2[i].rbegin(),nxt2[i].rend());
for(auto x:nxt2[i])s.push_back(x);
}
/*
for(auto i:f)cout << i<<" ";
cout <<'\n';
for(auto i:s)cout<<i<<" ";
cout << '\n';
*/
vector<bool> vis(N+1,0);
vector<int> res;
int pp = 0;
for(int p=0;p<(int)s.size();p++){
if(vis[s[p]])continue;
while(vis[f[pp]])pp++;
if(f[pp] == s[p])continue;
vis[f[pp]] = 1;
vis[s[p]] = 1;
res.push_back(f[pp]);
res.push_back(s[p]);
}
for(int i=0;i<N;i++){
if(!vis[i])res.push_back(i); // hahahahah
}
/*
for(auto i:res)cout<<i<<" ";
cout<<'\n';
*/
return res;
}
