#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)(a.size())
#define fi first
#define se second
typedef long long int ll;
typedef pair<int,int> pii;
//1)root at 0
//2)find centroid, centroid is the node with smallest subtree size that is also >= n/2
const int MAXN = 111111;
int dist[4][MAXN];
vector<int> createFunTour(int n, int q) {
if(n==2)return {0,1};
//hoursRequired(0, N - 1);
//attractionsBehind(0, N - 1);
//extract centroid
vector<int>sub(n,0);
sub[0] = n;
int cen = 0;
for(int i=1;i<n;i++){
sub[i] = attractionsBehind(0,i);
if(2*sub[i] >= n && sub[i] < sub[cen])cen = i;
}
//extract children
vector<int>ch;
vector<int>subtree[3];
for(int i=0;i<n;i++){
if(i==cen)continue;
dist[3][i] = hoursRequired(cen,i);
if(dist[3][i] == 1)ch.pb(i);
}
assert(sz(ch)>=2 && sz(ch)<=3);
//get children subtrees
vector<bool>vis(n,0);
vis[cen] = 1;
for(int i=0;i<2;i++){
for(int v=0;v<n;v++){
if(v==cen)continue;
dist[i][v] = hoursRequired(ch[i],v);
if(dist[3][v] == dist[i][v] + 1){
subtree[i].pb(v);
vis[v] = 1;
}
}
}
for(int v=0;v<n;v++){
if(!vis[v])subtree[2].pb(v);
}
set<pii,greater<pii>>s[3];
for(int x:subtree[0])s[0].insert({dist[3][x],x});
for(int x:subtree[1])s[1].insert({dist[3][x],x});
for(int x:subtree[2])s[2].insert({dist[3][x],x});
vector<int>ans;
function<bool(int)>check = [&](int i){ //check if j and k can be merged tgt
int j = (i+1)%3;
int k = (j+1)%3;
return sz(s[i]) == sz(s[j]) + sz(s[k]);
};
function<void(int)>merge = [&](int i){ //merge j and k
//merge j and k into one
int j = (i+1)%3;
int k = (j+1)%3;
set<pii,greater<pii>>tmp = s[j];
for(auto x : s[k])tmp.insert(x);
s[0] = s[i];
s[1] = tmp;
s[2].clear();
};
vector<int>debug;
function<void(int)>add = [&](int i){
ans.pb(s[i].begin()->se);
debug.pb(s[i].begin()->fi);
s[i].erase(s[i].begin());
};
//cout<<sz(s[0])<<" "<<sz(s[1])<<" "<<sz(s[2])<<'\n';
/*
cout<<cen<<'\n';
for(int x:ch)cout<<x<<" ";
cout<<'\n';
cout<<"s0"<<'\n';
for(auto x:s[0])cout<<x.fi<<" ";
cout<<'\n';
cout<<"s1"<<'\n';
for(auto x:s[1])cout<<x.fi<<" ";
cout<<'\n';
cout<<"s2"<<'\n';
for(auto x:s[2])cout<<x.fi<<" ";
cout<<'\n';
*/
if(!s[2].empty()){
if(sz(s[0]) >= sz(s[1]) + sz(s[2])){
merge(0);
goto jump;
}
else if(sz(s[1]) >= sz(s[0]) + sz(s[2])){
merge(1);
goto jump;
}
else if(sz(s[2]) >= sz(s[0]) + sz(s[1])){
merge(2);
goto jump;
}
int i = 0;
if(s[1].begin()->fi > s[i].begin()->fi)i = 1;
if(s[2].begin()->fi > s[i].begin()->fi)i = 2;
//reduce to two sub if possible
while(true){
assert(sz(s[0]) < sz(s[1]) + sz(s[2]));
assert(sz(s[1]) < sz(s[0]) + sz(s[2]));
assert(sz(s[2]) < sz(s[0]) + sz(s[1]));
add(i);
int j = (i+1)%3;
int k = (j+1)%3;
if(check(j)){
//cout<<sz(s[0])<<" "<<sz(s[1])<<" "<<sz(s[2])<<'\n';
if(!s[k].empty() && s[k].begin()->fi > debug.back())add(k);
merge(j);
goto jump;
}
if(check(k)){
//cout<<i<<" "<<j<<" "<<k<<'\n';
//cout<<s[i].begin()->fi<<" "<<s[j].begin()->fi<<" "<<s[k].begin()->fi<<'\n';
//cout<<sz(s[0])<<" "<<sz(s[1])<<" "<<sz(s[2])<<'\n';
if(!s[j].empty() && s[j].begin()->fi > debug.back())add(j);
merge(k);
goto jump;
}
assert(!s[j].empty() && !s[k].empty());
i = j;
if(s[j].begin()->fi < s[k].begin()->fi)i = k;
}
}
jump:
int cur = 0;
while(!s[cur].empty()){
//cout<<cur<<" "<<s[cur].begin()->fi<<'\n';
add(cur);
cur^=1;
}
cur^=1;
assert(sz(s[cur]) <= 1);
while(!s[cur].empty())add(cur);
ans.pb(cen);
// for(int i=0;i+1<n;i++){
// cout<<debug[i]<<'\n';
// if(i && debug[i-1] + debug[i] < debug[i] + debug[i+1]){
// cout<<debug[i+1]<<'\n';
// break;
// }
// }
return ans;
}
