#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]==1) 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>,greater <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;
if (s[2].empty()){
if (s[0].size()<s[1].size()) swap(s[0],s[1]);
for (int i=0; i<N-1; i++){
if (i%2==0){
op.push_back((*s[0].begin()).second);
s[0].erase(s[0].begin());
} else {
op.push_back((*s[1].begin()).second);
s[1].erase(s[1].begin());
}
}
} else {
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={-1,-1};
int ha=-1;
for (int i=0; i<3; i++){
if (prv==i||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 (prv==-1){
int nxt=(w+1)%3;
for (auto j:s[(nxt+1)%3]) s[nxt].insert(j);
while (!s[w].empty()){
op.push_back((*s[w].begin()).second); s[w].erase(s[w].begin());
op.push_back((*s[nxt].begin()).second); s[nxt].erase(s[nxt].begin());
}
} else if (s[w].size()){
int rem=3-w-prv;
if ((*s[rem].begin()).first>=(*s[w].begin()).first){
int f=1;
while (!s[w].empty()){
if (f){
pair <int,int> tp=*s[rem].begin();
op.push_back(tp.second);
for (auto j:s[rem]) s[prv].insert(j);
s[prv].erase(tp);
} else {
op.push_back((*s[prv].begin()).second);
s[prv].erase(s[prv].begin());
}
op.push_back((*s[w].begin()).second);
s[w].erase(s[w].begin());
f=0;
}
} else {
for (auto j:s[rem]) s[prv].insert(j);
while (!s[w].empty()){
op.push_back((*s[w].begin()).second);
s[w].erase(s[w].begin());
op.push_back((*s[prv].begin()).second);
s[prv].erase(s[prv].begin());
}
}
}
}
op.push_back(rt);
return op;
}
