#include<bits/stdc++.h>
#include "fun.h"
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
cerr<<h;
if(sizeof...(t)){
cerr<<", ";
}
debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
std::vector<int> createFunTour(int n, int Q) {
if(n==2)return {0, 1};
//int H = hoursRequired(0, N - 1);
//int A = attractionsBehind(0, N - 1);
vi siz(n), dep(n), typ(n);
siz[0]=n;
int cent=0;
for(int i=1; i<n; i++){
siz[i]=attractionsBehind(0, i);
if(2*siz[i]>=n && siz[i]<siz[cent])cent=i;
}
vi kto;
for(int i=0; i<n; i++){
if(i!=cent)dep[i]=hoursRequired(cent, i);
if(dep[i]==1)kto.pb(i);
}
set<pii> S[3];
for(int i=0; i<kto.size(); i++){
S[i].insert(mp(1, kto[i]));
typ[kto[i]]=i;
}
typ[cent]=-1;
for(int i=0; i<n; i++){
if(dep[i]>1){
if(attractionsBehind(i, kto[0])*2>n){
S[0].insert(mp(dep[i], i));
typ[i]=0;
}
else if(attractionsBehind(i, kto[1])*2>n){
S[1].insert(mp(dep[i], i));
typ[i]=1;
}
else{
S[2].insert(mp(dep[i], i));
typ[i]=2;
}
}
}
vi ans;
int lst=0, opt=S[0].crbegin()->st;
for(int i=1; i<kto.size(); i++)if(opt<S[i].crbegin()->st){
lst=i;
opt=S[i].crbegin()->st;
}
ans.pb(S[lst].crbegin()->nd);
S[lst].erase(--S[lst].end());
while(max({S[0].size(), S[1].size(), S[2].size()})*2<S[0].size()+S[1].size()+S[2].size()){
int akt=(lst+1)%3;
opt=S[akt].crbegin()->st;
if(opt<S[(akt+1)%3].crbegin()->st){
akt=(akt+1)%3;
opt=S[(akt+1)%3].crbegin()->st;
}
lst=akt;
ans.pb(S[lst].crbegin()->nd);
S[lst].erase(--S[lst].end());
}
if(S[0].size()<S[1].size()){
swap(S[0], S[1]);
if(lst==0 || lst==1)lst^=1;
}
if(S[0].size()<S[2].size()){
swap(S[0], S[2]);
if(lst==0 || lst==2)lst^=2;
}
if(lst!=0 && S[lst^3].size() && S[lst^3].crbegin()->st>dep[ans.back()]){
ans.pb(S[lst^3].crbegin()->nd);
S[lst^3].erase(--S[lst^3].end());
lst^=3;
}
for(auto i:S[2]){
S[1].insert(i);
}
if(S[0].size()>S[1].size())S[1].insert(mp(0, cent));
else if(S[0].size()<S[1].size())S[0].insert(mp(0, cent));
else if(lst==0)S[1].insert(mp(0, cent));
else S[0].insert(mp(0, cent));
lst=min(lst, 1);
while(ans.size()<n){
lst^=1;
ans.pb(S[lst].crbegin()->nd);
S[lst].erase(--S[lst].end());
}
for(int i=1; i<n; i++){
//deb(ans[i], ans[i-1], hoursRequired(ans[i], ans[i-1]))
}
for(int i:ans){
//cerr<<i<<" ";
}
return ans;
}
