#include <iostream>
#include <vector>
#include <set>
#include "fun.h"
using namespace std;
const int M = 1<<17;
vector<int> nei[M];
set<pair<int, int>> st[M];
int Par[M], hei[M], Er[M];
void dfs(int u, int p, int h = 1){
Par[u] = p;
hei[u] = h;
for (int i=0;i<nei[u].size();i++){
if (nei[u][i] == p)
nei[u].erase(begin(nei[u]) + i);
}
for (int i : nei[u]){
// cout<<u<<" --> "<<i<<endl;
dfs(i, u, h + 1);
for (auto [x, y] : st[i])
st[u].insert({x, y});
}
st[u].insert({h, u});
}
int getFar(int u){
int dst = 0, v = u, ansV;
// cout<<v<<" :: "<<endl;;
if (st[u].size() > 1)
dst = (*rbegin(st[u])).first - hei[v], ansV = (*rbegin(st[u])).second;
while (Par[u] != -1){
u = Par[u];
for (int i : nei[u]){
if (st[i].find({hei[v], v}) == st[i].end() and st[i].size() > 0){
// cout<<u<<','<<i<<' ';
// for (auto [x, y] : st[i])
// cout<<"{"<<x<<','<<y<<"} ";
// cout<<endl;
auto [x, y] = *rbegin(st[i]);
if (x + hei[v] - 2 * hei[u] > dst)
dst = x + hei[v] - 2 * hei[u], ansV = y;
}
}
if (Er[u] == 0 and hei[v] - hei[u] > dst)
dst = hei[v] - hei[u], ansV = u;
}
return ansV;
}
void Erase(int u){
int v = u;
while (u != -1){
st[u].erase({hei[v], v});
u = Par[u];
}
Er[v] = 1;
}
vector<int> createFunTour(int n, int q){
if (n <= 500){
for (int i=0;i<n;i++){
for (int j=0;j<n;j++)
if (i != j and hoursRequired(i, j) == 1)
nei[i].push_back(j);
}
}
else{
for (int i=1;i<n;i++){
int p = (i - 1) / 2;
nei[p].push_back(i);
nei[i].push_back(p);
}
}
dfs(0, -1);
vector<int> ans = {0};
for (int i=1;i<n;i++){
if (hei[i] > hei[ans.back()])
ans = {i};
}
for (int i=1;i<n;i++){
int v = getFar(ans.back());
// cout<<ans.back()<<' '<<v<<endl;
Erase(ans.back());
ans.push_back(v);
}
return ans;
}
