#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define S(A) sort(A.begin(),A.end())
typedef vector<pair<int,int>> VP;
vector<int>ans;
#define PB push_back
void makedouble(VP a,VP b){
S(b),S(a);
while(a.size()||b.size()){
ans.PB(b.back().second);
b.pop_back();
swap(a,b);
}
}
VP concat(VP a,VP b){
for(auto i:b)
a.PB(i);
return a;
}
void stuff(VP W[3],int a,int b,int c,int k){
if(k-a) makedouble(concat(W[b],W[c]),W[a]);
else makedouble(W[a],concat(W[b],W[c]));
}
vector<int> createFunTour(int N, int Q) {
if(N==2) return{0,1};
pair<int,int>centroid{N,0};
for(int i=1;i<N;i++) {
int k=attractionsBehind(0,i);
if(k>=(N+1)/2)
centroid=min(centroid,{k,i});
}
int k=centroid.second;
vector<int>subtreez;
VP W[3];
for(int i=0;i<N;i++){
if(i==k) continue;
int C=hoursRequired(k,i);
if(!subtreez.size()){
subtreez.PB(i);
W[0].PB({C,i});
} else if(subtreez.size()==1){
if(W[0][0].first+C-hoursRequired(W[0][0].second,i))
W[0].PB({C,i});
else subtreez.PB(i),W[1].PB({C,i});
} else {
if(W[0][0].first+C-hoursRequired(W[0][0].second,i))
W[0].PB({C,i});
else if(W[1][0].first+C-hoursRequired(W[1][0].second,i))
W[1].PB({C,i});
else W[2].PB({C,i});
}
}
S(W[0]),S(W[1]),S(W[2]);
sort(W,W+3,[](VP &a,VP &b){
return a.size()>b.size();
});
if(W[2].empty()){
makedouble(W[1],W[0]);
} else if(W[0].size()>=W[1].size()+W[2].size()){
makedouble(concat(W[1],W[2]), W[0]);
} else {
sort(W,W+3,[](VP &a,VP &b){
return a.back()>b.back();
});
int prv=0;
ans.PB(W[0].back().second);
W[0].pop_back();
while(1){
int A=W[0].size(),B=W[1].size(),C=W[2].size();
if(A+B==C){
stuff(W,2,0,1,prv);
break;
} else if (A+C==B){
stuff(W,1,2,0,prv);
break;
} else if (B+C==A){
stuff(W,0,1,2,prv);
break;
}
pair<int,int>s{0,0};
for(int i=0;i<3;i++)
if(i-prv)s=max(s,{W[i].back().first,i});
prv=s.second;
ans.PB(W[prv].back().second);
W[prv].pop_back();
}
}
ans.PB(k);
return ans;
}
