#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);
}
//get children subtrees
for(int i=0;i<sz(ch);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);
}
}
//cout<<"cen "<<cen<<'\n';
//for(int x:ch)cout<<x<<" ";
//cout<<'\n';
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;
auto tmp = s[j];
for(auto x : s[k])tmp.insert(x);
s[0] = s[i];
s[1] = tmp;
s[2].clear();
};
function<void(int)>add = [&](int i){
ans.pb(s[i].begin()->se);
s[i].erase(s[i].begin());
};
if(sz(s[2])){
//assert(sz(s[0]) + sz(s[1]) >= sz(s[2]));
//assert(sz(s[1]) + sz(s[2]) >= sz(s[0]));
//assert(sz(s[0]) + sz(s[2]) >= sz(s[1]));
//three subtrees
int i = 0;
if(s[1].begin()->fi > s[0].begin()->fi)i = 1;
if(s[2].begin()->fi > s[1].begin()->fi)i = 2;
int j = (i+1)%3;
int k = (j+1)%3;
//reduce to two sub if possible
if(check(i))merge(i);
else if(check(j))merge(j);
else if(check(k))merge(k);
else{
while(true){
//assert(!s[i].empty());
add(i);
j = (i+1)%3;
k = (j+1)%3;
if(check(i)){
merge(i);
swap(s[0],s[1]);
}
if(check(j)){
if(!s[k].empty() && s[k].begin()->fi > s[j].begin()->fi)add(k);
merge(j);
break;
}
if(check(k)){
if(!s[j].empty() && s[j].begin()->fi > s[k].begin()->fi)add(j);
merge(k);
break;
}
if(s[j].begin()->fi > s[k].begin()->fi)i = j;
else i = k;
}
}
}
int cur = 0;
while(!s[cur].empty()){
add(cur);
cur^=1;
}
while(!s[cur].empty())add(cur);
ans.pb(cen);
return ans;
}
