#include "fun.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector <int> createFunTour(int N,int Q){
int sz[N];
for (int i=0; i<N; i++) sz[i]=attractionsBehind(0,i);
int rt=0,mn=N;
for (int i=1; i<N; i++){
if (2*sz[i]>N&&sz[i]<mn){
mn=sz[i];
rt=i;
}
}
int dep[N];
for (int i=0; i<N; i++) dep[i]=hoursRequired(rt,i);
if (N==2) return {0,1};
vector <int> neigh;
for (int i=0; i<N; i++) if (dep[i]) neigh.push_back(i);
int col[N];
for (int i=0; i<N; i++){
col[i]=2;
for (int j=0; j<2; j++){
if (hoursRequired(neigh[j],i)+1==dep[i]){
col[i]=j;
break;
}
}
if (i==rt) col[i]=-1;
}
set <pair <int,int> > s[3];
for (int i=0; i<N; i++) if (col[i]!=-1) s[col[i]].insert({dep[i],i});
vector <int> op;
op.push_back(rt);
int prv=-1;
while (s[0].size()!=s[1].size()+s[2].size()&&s[1].size()!=s[0].size()+s[2].size()&&s[2].size()!=s[0].size()+s[1].size()){
pair <int,int> best={1e9,1e9};
int ha=0;
for (int i=0; i<3; i++){
if (i==prv||s[i].empty()) continue;
pair <int,int> tp=*s[i].begin();
if (tp<best){
best=tp;
ha=i;
}
}
op.push_back(best.second);
prv=ha;
s[ha].erase(best);
}
int w=2;
if (s[0].size()==s[1].size()+s[2].size()) w=0;
else if (s[1].size()==s[0].size()+s[2].size()) w=1;
if (w==prv){
while (!s[w].empty()){
pair <int,int> best={1e9,1e9};
int ha=0;
for (int i=0; i<3; i++){
if (i==w||s[i].empty()) continue;
pair <int,int> tp=*s[i].begin();
if (tp<best){
best=tp;
ha=i;
}
}
op.push_back(best.second);
s[ha].erase(best);
pair <int,int> tp=*s[w].begin();
op.push_back(tp.second);
s[w].erase(tp);
}
} else {
while (!s[w].empty()){
pair <int,int> tp=*s[w].begin();
op.push_back(tp.second);
s[w].erase(tp);
pair <int,int> best={1e9,1e9};
int ha=0;
for (int i=0; i<3; i++){
if (i==w||s[i].empty()) continue;
tp=*s[i].begin();
if (tp<best){
best=tp;
ha=i;
}
}
op.push_back(best.second);
s[ha].erase(best);
}
}
reverse(op.begin(),op.end());
return op;
}
