#include<bits/stdc++.h>
#include "fun.h"
using namespace std;
vector<int>ans,av(3),dist,grup[3];
int cmp(int a,int b)
{
return dist[a]<dist[b];
}
int cmp2(int a,int b)
{
return grup[a].size()>grup[b].size();
}
int cmp3(int a,int b)
{
return dist[grup[a].back()]>dist[grup[b].back()];
}
vector<int>createFunTour(int n,int q)
{
dist.resize(n);
int cent=0,last=-1,i,j;
for(i=1;i<n;i++)
if (attractionsBehind(cent,i)>n/2)
cent=i;
for(i=0;i<n;i++)
if (i!=cent)
dist[i]=hoursRequired(i,cent);
for(i=0;i<n;i++)
if (i!=cent){
for(j=0;j<3;j++)
if (j==2 || grup[j].size()==0 || hoursRequired(grup[j][0],i)!=(dist[i]+dist[grup[j][0]])){
grup[j].push_back(i);
break;
}
}
av[0]=0;
av[1]=1;
av[2]=2;
for(i=0;i<3;i++)
sort(grup[i].begin(),grup[i].end(),cmp);
while(1){
sort(av.begin(),av.end(),cmp2);
if (grup[av[0]].size()>=grup[av[1]].size()+grup[av[2]].size())
break;
sort(av.begin(),av.end(),cmp3);
if (last==av[0])
last=av[1];
else
last=av[0];
ans.push_back(grup[last].back());
grup[last].pop_back();
}
grup[av[1]].insert(grup[av[1]].end(),grup[av[2]].begin(),grup[av[2]].end());
sort(grup[av[1]].begin(),grup[av[1]].end(),cmp);
int aux=0;
if (ans.size()>1 && dist[ans.back()]<dist[grup[av[1]].back()])
aux=1;
while(grup[av[aux]].size()){
ans.push_back(grup[av[aux]].back());
grup[av[aux]].pop_back();
aux=aux^1;
}
ans.push_back(cent);
return ans;
}
