#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
std::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;
vector<pair<int,int>> why[3];
for(int i=0;i<N;i++){
if(i==k) continue;
int C=hoursRequired(k,i);
if(!subtreez.size()){
subtreez.push_back(i);
why[0].push_back({C,i});
} else if(subtreez.size()==1){
if(why[0][0].first+C-hoursRequired(why[0][0].second,i))
why[0].push_back({C,i});
else subtreez.push_back(i),why[1].push_back({C,i});
} else {
if(why[0][0].first+C-hoursRequired(why[0][0].second,i))
why[0].push_back({C,i});
else if(why[1][0].first+C-hoursRequired(why[1][0].second,i))
why[1].push_back({C,i});
else why[2].push_back({C,i});
}
}
sort(why[0].begin(),why[0].end());
sort(why[1].begin(),why[1].end());
sort(why[2].begin(),why[2].end());
sort(why,why+3,[](vector<pair<int,int>>&a,vector<pair<int,int>>&b){
if(a.empty()&&b.empty()) return false;
return a.size()-b.size()?a.size()>b.size():a.back().first>b.back().first;
});
vector<int>ans{why[0].back().second};
int prevdep=1e9,curdep=why[0].back().first,cursub=0;
why[0].pop_back();
while(ans.size()<N-1){
vector<int>compatible;
for(int i=0;i<3;i++)
if(why[i].size()&&i-cursub&&why[i].back().first<=prevdep)
compatible.push_back(i);
if(compatible.size()==1){
int c=compatible[0];
prevdep=curdep;cursub=c;
curdep=why[c].back().first;
ans.push_back(why[c].back().second);
why[c].pop_back();
} else {
int A=compatible[0];
int B=compatible[1];
int tot=why[0].size()+why[1].size()+why[2].size();
if(why[A].size()<why[B].size())
swap(A,B);
if(why[A].size()==why[B].size()){
if(why[A].back().first<why[B].back().first){
prevdep=curdep;cursub=B;
curdep=why[B].back().first;
ans.push_back(why[B].back().second);
why[B].pop_back();
} else {
prevdep=curdep;cursub=A;
curdep=why[A].back().first;
ans.push_back(why[A].back().second);
why[A].pop_back();
}
} else if(why[A].size()>=tot/2){
prevdep=curdep;cursub=A;
curdep=why[A].back().first;
ans.push_back(why[A].back().second);
why[A].pop_back();
} else if(why[B].size()>=tot/2){
prevdep=curdep;cursub=B;
curdep=why[B].back().first;
ans.push_back(why[B].back().second);
why[B].pop_back();
} else if(why[A].back().first<why[B].back().first){
prevdep=curdep;cursub=B;
curdep=why[B].back().first;
ans.push_back(why[B].back().second);
why[B].pop_back();
} else {
prevdep=curdep;cursub=A;
curdep=why[A].back().first;
ans.push_back(why[A].back().second);
why[A].pop_back();
}
}
}
ans.push_back(k);
return ans;
}
