#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,Min=sz;
}
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);
//cout << j << ' ' << i << '\n';
}
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';
int T=0;
vector<int> A,B;
if(S==2){
A=G[0];B=G[1];
if((int)A.size()>(int)B.size()) swap(A,B);
}
else{
int c=-1;
while(T<N-1){
int Max=0;
for(int i=0;i<S;i++) Max=max(Max,(int)G[i].size());
if(2*Max==N-T-1) break;
int u=-1;Max=0;
for(int i=0;i<S;i++){
if(c==i) continue;
if(D[G[i].back()]>Max) Max=D[G[i].back()],u=i;
}
assert(u!=-1);
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-1) u=i;
assert(u!=-1);
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];
});
assert((int)A.size()==(int)B.size());
}
while(!A.empty() || !B.empty()){
if(!B.empty()) P[T++]=B.back(),B.pop_back();
if(!A.empty()) P[T++]=A.back(),A.pop_back();
}
P[T++]=X;
//for(int i=0;i<N;i++) cout << P[i] << ' ';
//cout << '\n';
return P;
}
