#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> createFunTour(int N, int Q) {
vector<int> P(N);
int X=0,Min=N;
for(int i=0;i<N;i++){
int sz=attractionsBehind(0,i);
if(sz>N/2 && sz<Min) X=i;
}
vector<int> D(N),cc;
for(int i=0;i<N;i++){
D[i]=hoursRequired(X,i);
if(D[i]==1) cc.push_back(i);
}
int S=(int)cc.size();
vector<vector<int>> G(S);
for(int i=0;i<N;i++){
if(i==X) continue;
int j=0;
while(j+1<S && hoursRequired(cc[j],i)+D[cc[j]]!=D[i]) j++;
G[j].push_back(i);
}
for(int i=0;i<S;i++){
sort(G[i].begin(),G[i].end(),[&](int x,int y){
return D[x]>D[y];
});
}
//cout << X << '\n';
P[0]=X;
int T=1,c=-1;
while(T<N){
int Max=0;
for(int i=0;i<S;i++) Max=max(Max,(int)G[i].size());
if(2*Max==N-T) break;
int u=-1;Min=N;
for(int i=0;i<S;i++){
if(c==i) continue;
if(D[G[i].back()]<Min) Min=D[G[i].back()],u=i;
}
P[T++]=G[u].back();
G[u].pop_back();c=u;
}
int u=-1;
for(int i=0;i<S;i++) if(2*(int)G[i].size()==N-T) u=i;
vector<int> A,B;
for(int i=0;i<S;i++){
if(u==i) A=G[i];
else B.insert(B.end(),G[i].begin(),G[i].end());
}
if(c!=u) swap(A,B);
sort(A.begin(),A.end(),[&](int x,int y){
return D[x]>D[y];
});
sort(B.begin(),B.end(),[&](int x,int y){
return D[x]>D[y];
});
while(!A.empty()){
P[T++]=B.back();
P[T++]=A.back();
B.pop_back();
A.pop_back();
}
reverse(P.begin(),P.end());
return P;
}
