#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
using vi = vector<int>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
vvl g;
vll sz;
vpl lis;
void find_dep(ll cur, ll pr, ll d){
lis.pb({d,cur});
for(ll i:g[cur]){
if(i!=pr){
find_dep(i,cur, d+1);
}
}
}
void find_sz(ll cur, ll pr=-1){
sz[cur]=1;
for(ll i:g[cur]){
if(i!=pr){
find_sz(i,cur);
sz[cur]+=sz[i];
}
}
}
ll cen(ll cur, ll n, ll pr=-1){
for(ll i:g[cur]){
if(i!=pr){
if(sz[i]*2>n)return cen(i,n,cur);
}
}
return cur;
}
vi solve(ll cur, vvp mx, ll n){
vi ord, pri;
ll l = -1, o=-1;
while(n>0){
if(mx[0].size()>=(n+1)/2){o=0;break;}
if(mx[1].size()>=(n+1)/2){o=1;break;}
if(mx[2].size()>=(n+1)/2){o=2;break;}
ll x = -1;
for(ll i = 0; i < 3; ++i){
if(i==l || mx[i].empty())continue;
if(x==-1 || mx[i].back().f>mx[x].back().f)x=i;
}
l=x;
ord.pb(mx[x].back().s);
pri.pb(mx[x].back().f);
n--;
mx[x].pop_back();
}
if(ord.size()>1 && pri.back()<pri[pri.size()-2]){
while(n>0){
ll x=-1;
for(ll i = 0; i < 3; ++i){
if(i==o || mx[i].empty())continue;
if(x==-1 || mx[i].back().f>mx[x].back().f)x=i;
}
ord.pb(mx[x].back().s);
pri.pb(mx[x].back().f);
mx[x].pop_back();
n--;
if(n==0)break;
ord.pb(mx[o].back().s);
pri.pb(mx[o].back().f);
mx[o].pop_back();
n--;
}
}
else{
while(n>0){
ord.pb(mx[o].back().s);
pri.pb(mx[o].back().f);
mx[o].pop_back();
n--;
if(n==0)break;
ll x=-1;
for(ll i = 0; i < 3; ++i){
if(i==o || mx[i].empty())continue;
if(x==-1 || mx[i].back().f>mx[x].back().f)x=i;
}
ord.pb(mx[x].back().s);
pri.pb(mx[x].back().f);
mx[x].pop_back();
n--;
}
}
ord.pb(cur);
return ord;
}
std::vector<int> createFunTour(int n, int q) {
ll st = 0, am=n;
for(ll i = 1; i < n; ++i){
ll o = attractionsBehind(0, i);
if(o*2>=n && o<am){
am=o;
st=i;
}
}
vll dis(n);
vll ty;
for(ll i = 0; i < n; ++i){
if(i!=st){
dis[i] = hoursRequired(st,i);
if(dis[i]==1)ty.pb(i);
}
}
vvp mx(3);
for(ll i = 0; i < ty.size()-1; ++i){
for(ll j = 0; j < n; ++j){
if(dis[j]==0)continue;
ll o = hoursRequired(j, ty[i]);
if(o<dis[j]){
mx[i].pb({dis[j], j});
dis[j]=0;
}
}
}
for(ll j = 0; j < n; ++j){
if(dis[j]==0)continue;
mx[ty.size()-1].pb({dis[j], j});
dis[j]=0;
}
vi ans = solve(st, mx, n-1);
return ans;
}
