#include "fun.h"
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <set>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef vector < int > vi;
typedef pair < int, int > pii;
const int N = 1e5 + 500;
int root, siz[N], dep[N], ty[N], n;
vector < int > ch;
set < pii > mj[3];
void nadi_centroid(){
int bst = 0; siz[0] = n;
for(int i = 1;i < n;i++){
siz[i] = attractionsBehind(root, i);
if(2 * siz[i] >= n && siz[i] < siz[bst])
bst = i;
}
root = bst;
}
void nadi_udaljenost(){
for(int i = 0;i < n;i++){
if(i == root){
ty[i] = -1;
dep[i] = 0; continue;
}
dep[i] = hoursRequired(root, i);
if(dep[i] == 1){
ty[i] = (int)ch.size();
ch.PB(i);
}
}
}
void nadi_skupinu(){
for(int i = 0;i < n;i++){
if(i == root || dep[i] == 1) continue;
while(ty[i] + 1 < (int)ch.size() && dep[i] - 1 != hoursRequired(i, ch[ty[i]]))
ty[i]++;
}
}
vi perm2(){
mj[0].clear(); mj[1].clear(); mj[2].clear();
for(int i = 0;i < n;i++){
//printf("%d %d %d\n", i, ty[i], dep[i]);
if(!dep[i]) continue;
mj[ty[i]].insert({dep[i], i});
}
int zad = -1;
vi ans;
for(int i = 1;i < n;i++){
int bst = -1, krit = max(mj[0].size(), max(mj[1].size(), mj[2].size()));
for(int j = 0;j < (int)ch.size();j++){
if(j == zad) continue;
if(2 * krit >= n - i && (int)mj[j].size() != krit) continue;
if(!mj[j].size()) continue;
if(bst == -1 || (mj[j].rbegin() -> X) > dep[bst]){
bst = mj[j].rbegin() -> Y;
}
}
ans.PB(bst);
mj[ty[bst]].erase({dep[bst], bst});
zad = ty[bst];
}
ans.PB(root);
//printf("%d\n", root);
return ans;
}
// MAGIJA PREVARE
vi perm(){
for(int i = 0;i < n;i++){
//printf("%d %d %d\n", i, ty[i], dep[i]);
if(!dep[i]) continue;
mj[ty[i]].insert({dep[i], i});
}
int zad = -1;
vi ans;
for(int i = 1;i < n;i++){
int bst = -1, krit = max(mj[0].size(), max(mj[1].size(), mj[2].size()));
//printf("VELICINE %d %d %d\n", (int)mj[0].size(), (int)mj[1].size(), (int)mj[2].size());
//printf("krit = %d ost = %d\n", krit, n - i);
//if(2 * krit - 1 >= n - i)
// printf("KRITICNO!!!\n");
for(int j = 0;j < (int)ch.size();j++){
if(j == zad) continue;
if(2 * krit - 1 >= n - i && (int)mj[j].size() != krit) continue;
if(!mj[j].size()) continue;
if(bst == -1 || (mj[j].rbegin() -> X) > dep[bst]){
bst = mj[j].rbegin() -> Y;
}
}
//printf(" %d %d %d\n", bst, dep[bst], ty[bst]);
if(i > 2 && dep[ans[ans.size() - 2]] < dep[bst]){
return perm2();
}
ans.PB(bst);
mj[ty[bst]].erase({dep[bst], bst});
zad = ty[bst];
}
ans.PB(root);
//printf("%d\n", root);
return ans;
}
vi createFunTour(int nn, int q) {
n = nn; root = 0;
nadi_centroid();
nadi_udaljenost();
nadi_skupinu();
return perm();
}
