#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#include "fun.h"
// int hoursRequired(int x, int y){
// return 0;
// }
// int attractionsBehind(int x, int y){
// return 0;
// }
vector<int> createFunTour(int n, int q){
if (n == 1){
return {0};
}
if (n == 2){
return {0, 1};
}
vector<int> ans;
int root = 0;
for(int i = 1; i < n; ++i) if (attractionsBehind(root, i) >= (n+1) / 2)
root = i;
cout << "Centroid: " << root << endl;
vector<int> dis(n);
for(int i = 0; i < n; ++i) if (i != root) dis[i] = hoursRequired(root, i);
vector<int> direct_child;
for(int i = 0; i < n; ++i) if (dis[i] == 1) direct_child.push_back(i);
if (direct_child.size() == 2){
vector<int> v1, v2;
for(int i = 0; i < n; ++i) if (dis[i] >= 1){
if (hoursRequired(i, direct_child[0]) == dis[i]-1) v1.push_back(i);
else v2.push_back(i);
}
if (v1.size() > v2.size()) v2.push_back(root);
else v1.push_back(root);
if (v1.size() < v2.size()) swap(v1, v2);
sort(ALL(v1), [&dis](int x, int y){return dis[x] < dis[y];});
sort(ALL(v2), [&dis](int x, int y){return dis[x] < dis[y];});
while(v2.size()){
ans.push_back(v1.back()); ans.push_back(v2.back());
v1.pop_back(); v2.pop_back();
}
if (v1.size()) ans.push_back(v1.back());
}
else{
array<vector<int>, 3> v;
for(int i= 0; i < n; ++i) if (dis[i] >= 1){
for(int j = 0; j <= 2; ++j){
if (j == 2 || hoursRequired(i, direct_child[j]) == dis[i]-1) {
v[j].push_back(i);
break;
}
}
}
for(int j = 0; j < 3; ++j) sort(ALL(v[j]), [&dis](int x, int y){return dis[x] < dis[y];});
int u = -1, ma = -1;
for(int j = 0; j < 3; ++j) if (maximize(ma, dis[v[j].back()])) u = j;
while(true){
if (v[0].size() + v[1].size() + v[2].size() <= max({v[0].size(), v[1].size(), v[2].size()}) * 2) break;
ans.push_back(v[u].back());
v[u].pop_back();
int tmp = -1;
ma = -1;
for(int j = 0; j < 3; ++j) if (j != u){
if (maximize(ma, dis[v[j].back()]))
tmp = j;
}
u = tmp;
}
vector<int> v1, v2;
if (v[u].size() == max({v[0].size(), v[1].size(), v[2].size()})) {
v1 = v[u];
for(int j = 0; j < 3; ++j) if (j != u){
for(int k: v[j]) v2.push_back(k);
}
}
else{
v1 = v[u];
vector<vector<int>> vuto;
for(int j = 0; j < 3; ++j) if (j != u){
vuto.push_back(v[j]);
}
if (vuto[0].size() > vuto[1].size()) swap(vuto[0], vuto[1]);
for(int i: vuto[0]) v1.push_back(i);
v2 = vuto[1];
}
if (v1.size() <= v2.size()) v1.push_back(root);
else v2.push_back(root);
sort(ALL(v1), [&dis](int x, int y){return dis[x] < dis[y];});
sort(ALL(v2), [&dis](int x, int y){return dis[x] < dis[y];});
while(v2.size()){
ans.push_back(v1.back()); ans.push_back(v2.back());
v1.pop_back(); v2.pop_back();
}
if (v1.size()) ans.push_back(v1.back());
}
return ans;
}
// int main(void){
// ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
// clock_t start = clock();
// cerr << "Time elapsed: " << clock() - start << "ms!\n";
// return 0;
// }
