#include<bits/stdc++.h>
using namespace std;
#include "fun.h"
#define X first
#define Y second
#define pb push_back
#define getdis hoursRequired
#define getsz attractionsBehind
const int MAX=100005,mod=1e9+7,M=2000,inf=1e9;
void maxx(int &a,int b){if(b>a) a=b;}
using ii = pair < int ,int > ;
void minn(int &a,int b){if(b<a) a=b;}
void maxp(ii &a,ii b){if(b>a) a=b;}
void minp(ii &a,ii b){if(b<a) a=b;}
bool cp(ii &a,ii b){if(b>a) {a=b;return 1;}else return 0;}
void PL(int &a,int b){a+=b;if(a>=mod) a-=mod;}
///+++++++++++++++++++++++++++++
int a[MAX],sz[4],h[MAX];
bool vs[MAX];
int D[4];
short bel[MAX];
int L[4][MAX];
int getdeep(int v){
ii u = ii (0,0);
int r;
for(int i=1;i<=3;i++) if(i!=v && sz[i]!=0)
if( cp(u,ii(h[L[i][sz[i]]],sz[i])) ) r=i;
return r;
}
bool cmp(int u,int v){
return h[u]<h[v];}
std::vector<int> createFunTour(int n,int Q){
vector < int > vec;
a[0]=n;
if(n==2){
vec.pb(0);vec.pb(1);return vec;
}
int r=0;
for(int i=1;i<n;i++){
a[i]=getsz(0,i);
if(a[i]>n/2 && a[i]<a[r]) {
r=i;
}
}
int cn=0;
for(int i=0;i<n;i++)if(r!=i){
h[i]=getdis(r,i);
if(h[i]==1) D[++cn]=i;
}
vs[r]=1;
for(int i=1,u;i<=cn;i++){
u=D[i];
bel[u]=i;
L[i][1]=u;
vs[u]=1;
sz[i]=getsz(r,u);
///co the toi uu
}
int top[4]={1,1,1,1};
for(int i=0;i<n;i++) if(!vs[i]){
if(getdis(D[1],i)==h[i]-1){
bel[i]=1;
}
else{
if(getdis(D[2],i)==h[i]-1)
bel[i]=2;
else bel[i]=3;
}
L[bel[i]][++top[bel[i]]]=i;
//cout<<i<<' '<<bel[i]<<'\n';
}
for(int i=1;i<=cn;i++){
sort(L[i]+1,L[i]+1+sz[i],cmp);
}
int las=0;
int allsz=n;
bool okk=1;
for(int i=1;i<n && okk;i++){
int z=getdeep(las);
int v=L[z][sz[z]];
vec.pb(v);
sz[z]--;
allsz--;
las=z;
for(int i=1;i<=cn;i++)
if(sz[i]>=allsz/2){
okk=0;break;
}
}
if(!okk && allsz>1){
int sp;
for(int i=1;i<=cn;i++)
if(sz[i]>=allsz/2){
sp=i;break;
}
int z=getdeep(0);
if(z!=las && z!=sp){
int v=L[z][sz[z]];
vec.pb(v);
sz[z]--;
allsz--;
las=z;
}
bool turn=(las!=sp);
//for ( int u:vec) cout<<u<<' ';cout<<'\n';
//cout<<las<<' '<<sp<<'\n';
//cout<<allsz;return vec;
//cout<<sz[sp]<<' '<<allsz<<'\n';
while(allsz>1){
if(turn){
int z=sp;
if(sz[z]==0) {turn^=1;continue;}
int v=L[z][sz[z]];
vec.pb(v);
sz[z]--;
allsz--;
las=z;
}
else{
int z=getdeep(sp);
if(sz[z]==0) {turn^=1;continue;}
int v=L[z][sz[z]];
vec.pb(v);
sz[z]--;
allsz--;
las=z;
}
turn^=1;
}
}
vec.pb(r);
//cout<<allsz<<'\n';
return vec;
}
