#include "fun.h"
#define dbg(X) cerr<<#X<<": "<<X<<'\n';
#define cer(w_) {cerr<<#w_<<": ";for(ll i_ : w_) cerr<<i_<<" ";cerr<<'\n';}
#include "bits/stdc++.h"
using namespace std;
using ll = int;
const ll maxn = 100005;
ll n;
ll cen = 1;
ll sub(ll x,ll y){
return attractionsBehind(x-1,y-1);
}
ll dis(ll x,ll y){
return hoursRequired(x-1,y-1);
}
ll d[maxn];
vector<vector<ll> > w;
ll get(ll i){
assert(!w[i].empty());
ll ans = w[i].back();
w[i].pop_back();
return ans;
}
vector<int> createFunTour(int N, int Q) {
n = N;
if(n==2) return {0,1};
for(ll i = 1;i<=n;i++){
if(sub(cen,i)>n/2) cen = i;
}
vector<ll> v;
for(ll i = 1;i<=n;i++){
d[i] = dis(cen,i);
if(d[i]==1) v.push_back(i);
}
w.resize(v.size());
for(ll i = 1;i<=n;i++){
bool naso = 0;
if(i==cen) continue;
for(ll e = 0;!naso&&e<v.size()-1;e++){
if(sub(i,v[e])<=n/2) continue;
w[e].push_back(i);
naso = 1;
}
if(!naso){
w[v.size()-1].push_back(i);
}
}
sort(w.begin(),w.end(),[](const vector<ll> &v,const vector<ll> &v2){
return v.size()<v2.size();
});
for(ll e = 0;e<w.size();e++){
sort(w[e].begin(),w[e].end(),[](const ll &i, const ll &j){
return d[i]<d[j];
});
}
vector<ll> ans;
ll poc,last;
if(w.size()>=3){
ll epoc = 0;
for(ll e = 0;e<3;e++){
if(d[w[epoc].back()]<d[w[e].back()]) epoc = e;
}
poc = get(epoc);
last = epoc;
ans.push_back(poc);
ll su = w[0].size() + w[1].size() + w[2].size();
ll mx = max({w[0].size(),w[1].size(),w[2].size()});
while(su-mx-mx>0){
// dbg(ans.size());
// for(ll e = 0;e<w.size();e++) cer(w[e]);
ll cur = -1;
for(ll e = 0;e<3;e++){
if(e==last) continue;
if(cur==-1||d[w[cur].back()]<d[w[e].back()]) cur = e;
}
ll nxt = get(cur);
ans.push_back(nxt);
last = cur;
su = w[0].size() + w[1].size() + w[2].size();
mx = max({w[0].size(),w[1].size(),w[2].size()});
}
// cerr<<"PRESTO"<<'\n';
// dbg(ans.back());
vector<ll> id(w.size());
vector<ll> rev(w.size());
iota(id.begin(),id.end(),0);
sort(id.begin(),id.end(),[](const ll &i, const ll &j){
if(w[i].size()!=w[j].size()) return w[i].size()>w[j].size();
return w[i][0]<w[j][0];
});
for(ll e = 0;e<id.size();e++) rev[id[e]] = e;
sort(w.begin(),w.end(),[](const vector<ll> &v,const vector<ll> &v2){
if(v.size()!=v2.size()) return v.size()>v2.size();
return v[0]<v2[0];
});
// dbg(ans.size());
// dbg(last);
// for(ll e = 0;e<w.size();e++) cer(w[e]);
last = rev[last];
// dbg(last);
if(w.back().empty()){
w.pop_back();
if(last==2){
if(w[0].size()>w[1].size()) last = 0;
else last = 1;
}
}else{
ll f = last^3;
if(last!=0&&d[w[f].back()]>d[ans.back()]){
ll nxt = get(f);
ans.push_back(nxt);
last = 1;
// cerr<<"UZO?"<<'\n';
}
if(last==2) last = 1;
while(!w[2].empty()) w[1].push_back(get(2));
w.pop_back();
sort(w[1].begin(),w[1].end(),[](const ll &i, const ll &j){
return d[i]<d[j];
});
}
}else{
poc = get(1);
last = 1;
ans.push_back(poc);
}
// cer(ans);
// dbg(last);
// for(ll e = 0;e<w.size();e++) cer(w[e]);
while(w[0].size()||w[1].size()){
// cerr<<w[0].size()<< " "<<w[1].size()<<'\n';
ll cur = last^1;
ll nxt = get(cur);
ans.push_back(nxt);
last = cur;
}
ans.push_back(cen);
// cer(ans);
for(ll &x : ans) x--;
return ans;
}
