#include <bits/stdc++.h>
#include <fun.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
int n;
vector<int> dist;
int get_centroid(){
int ind=0,val=n;
for(int i=1;i<n;i++){
int num=attractionsBehind(0,i);
if(num>=(n+1)/2){
if(ind==-1 || val>num){
ind=i;
val=num;
}
}
}
return ind;
}
vector<int> deg2(int c,int x,int y){
vector<pii> part1;
vector<pii> part2;
for(int i=0;i<n;i++){
if(i==c) continue;
if(attractionsBehind(i,x)>n/2){
part1.push_back(mp(dist[i],i));
} else part2.push_back(mp(dist[i],i));
}
if(part1.size()<=part2.size()) part1.push_back(mp(0,c));
else part2.push_back(mp(0,c));
sort(part1.begin(),part1.end());
sort(part2.begin(),part2.end());
int ind1=part1.size()-1;
int ind2=part2.size()-1;
vector<int> ans;
for(int i=0;i<n;i++){
if(i%2==0){
ans.push_back(part1[ind1].se);
ind1--;
} else{
ans.push_back(part2[ind2].se);
ind2--;
}
}
return ans;
}
vector<int> deg3(int c,int x,int y,int z){
vector<int> ans;
vector<pii> part[3];
for(int i=0;i<n;i++){
if(i==c) continue;
if(attractionsBehind(i,x)>n/2){
part[0].push_back(mp(dist[i],i));
} else if(attractionsBehind(i,y)>n/2){
part[1].push_back(mp(dist[i],i));
} else part[2].push_back(mp(dist[i],i));
}
int siz[3];
for(int i=0;i<3;i++) siz[i]=part[i].size();
int mnind=0;
for(int i=1;i<3;i++) if(siz[i]<siz[mnind]) mnind=i;
part[mnind].push_back(mp(0,c));
siz[mnind]++;
for(int i=0;i<3;i++) sort(part[i].begin(),part[i].end());
int prev=-1;
while(siz[0]!=siz[1]+siz[2] && siz[1]!=siz[2]+siz[0] && siz[2]!=siz[0]+siz[1]){
int mx=0;
int ind;
for(int i=0;i<3;i++){
if(i==prev) continue;
if(part[i][siz[i]-1].fi>mx){
mx=part[i][siz[i]-1].fi;
ind=i;
}
}
ans.push_back(part[ind][siz[ind]-1].se);
siz[ind]--;
prev=ind;
}
for(int i=0;i<3;i++){
if(2*siz[i]==siz[0]+siz[1]+siz[2]){
vector<pii> u,v;
for(int j=0;j<siz[i];j++) u.push_back(part[i][j]);
for(int k=0;k<3;k++){
if(k==i) continue;
for(int j=0;j<siz[k];j++) v.push_back(part[k][j]);
}
sort(u.begin(),u.end());
sort(v.begin(),v.end());
bool swu=true;
if(prev==i || prev==-1) swu=false;
else{
for(int j=0;j<3;j++){
if(j==prev) continue;
if(j==i) continue;
if(part[j][siz[j]-1].fi>part[prev][siz[prev]].fi) swu=false;
}
}
for(int j=siz[i]-1;j>=0;j--){
if(!swu){
ans.push_back(v[j].se);
ans.push_back(u[j].se);
} else{
ans.push_back(u[j].se);
ans.push_back(v[j].se);
}
}
return ans;
}
}
}
vector<int> createFunTour(int nn, int q){
n=nn;
int c=get_centroid();
for(int i=0;i<n;i++){
if(i==c) dist.push_back(0);
else dist.push_back(hoursRequired(c,i));
}
int cnt=0;
vector<int> roots;
for(int i=0;i<n;i++) if(dist[i]==1){
cnt++;
roots.push_back(i);
}
if(cnt==1) return {0,1};
if(cnt==2) return deg2(c,roots[0],roots[1]);
else return deg3(c,roots[0],roots[1],roots[2]);
}
