#include "fun.h"
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define REP1(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int maxn=1e3+5;
#define REP(i,n) for(int i=0;i<n;i++)
int dist[maxn][maxn];
bool vis[maxn];
vector<int> v[maxn];
int dep[maxn];
deque<int> vv[maxn];
void dfs(int u){
vv[dep[u]].pb(u);
for(int x:v[u]){
dep[x]=dep[u]+1;
dfs(x);
}
}
int get(int a,int b){
int d=0;
while(a!=b){
if(dep[a]>dep[b]){
a=(a-1)/2;
}
else b=(b-1)/2;
++d;
}
return d;
}
vector<int> createFunTour(int n, int q) {
if(n>500){
REP1(i,n-1){
v[(i-1)/2].pb(i);
}
dfs(0);
int st=n-1;
vector<int> ans;
REP(i,n){
ans.pb(st);
int mx=0,p=0;
for(int j=19;j>=0;j--){
if(sz(vv[j])){
int a=vv[j][0];
if(get(st,a)>mx){
mx=get(st,a);
p=a;
}
a=vv[j].back();
if(get(st,a)>mx){
mx=get(st,a);
p=a;
}
}
}
st=p;
}
}
int st=0,mx=0;
REP(i,n){
REP(j,i){
dist[i][j]=hoursRequired(i,j);
if(dist[i][j]>mx){
mx=dist[i][j];
st=i;
}
}
}
REP(i,n){
REP(j,n){
if(!dist[i][j]) dist[i][j]=dist[j][i];
}
}
vector<int> ans;
REP(asd,n){
ans.push_back(st);
vis[st]=1;
int mx=0,p=0;
REP(j,n){
if(!vis[j]){
if(dist[st][j]>mx){
mx=dist[st][j];
p=j;
}
}
}
st=p;
}
return ans;
}
