#include "fun.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
const int B = 894;
int d[B][B];
const int MAXN = 1e5 + 5;
vector<int> edges[MAXN];
bool check = false;
vector<int> createFunTour(int n, int Q) {
if(n <= B && check){
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
d[i][j] = d[j][i] = hoursRequired(i, j);
}
}
vector<int> used(n);
auto get = [&](int a){
int b = a;
for(int i=0;i<n;i++){
if(used[i]) continue;
if(d[i][a] > d[b][a]) b = i;
} return b;
};
int a = 0, b = 0;
b = get(a);
vector<int> p; p.push_back(b);
used[b] = 1;
while((int)p.size() < n){
a = get(b);
p.push_back(a);
used[a] = 1;
b = a;
} return p;
}
for(int i=0;2*i+1<n;i++){
edges[i].push_back(2*i+1);
edges[2*i+1].push_back(i);
if(2*i+2<n){
edges[i].push_back(2*i+2);
edges[2*i+2].push_back(i);
}
}
vector<int> sub(n), d(n);
function<void(int, int)> dfs = [&](int u, int p){
sub[u] = 1;
for(auto x : edges[u]){
if(x == p) continue;
dfs(x, u);
sub[u] += sub[x];
}
}; dfs(0, 0);
//~ cout<<"here"<<endl;
function<int(int, int)> cen = [&](int u, int p){
for(auto x : edges[u]){
if(x == p) continue;
if(sub[x] * 2 > n) return cen(x, u);
} return u;
};
int C = cen(0, 0);
cout<<C<<endl;
function<void(int, int, priority_queue<ar<int, 2>>&)> dfs2 = [&](int u, int p, priority_queue<ar<int, 2>>& pq){
pq.push({d[u], u});
for(auto x : edges[u]){
if(x == p) continue;
d[x] = d[u] + 1;
dfs2(x, u, pq);
}
};
int sz = edges[C].size();
vector<priority_queue<ar<int, 2>>> v(sz);
for(int i=0;i<sz;i++){
dfs2(edges[C][i], C, v[i]);
}
vector<int> p;
int last = -1;
while((int)p.size() < n - 1){
vector<int> t(sz); iota(t.begin(), t.end(), 0);
sort(t.begin(), t.end(), [&](int i, int j){
if(v[i].empty()) return false;
if(v[j].empty()) return true;
return (v[i].top()[0] > v[j].top()[0]);
});
int a = t[0], b = t[1];
if(sz > 2 && !v[t[2]].empty()){
if(v[t[0]].size() + v[t[1]].size() - 2 < v[t[2]].size()){
a = t[0], b = t[2];
}
}
if(last == a) swap(a, b);
if(!v[a].empty()) p.push_back(v[a].top()[1]), v[a].pop();
if(!v[b].empty()) p.push_back(v[b].top()[1]), v[b].pop();
last = b;
}
p.push_back(C);
//~ for(auto x : p) cout<<x<<" ";
//~ cout<<endl;
return p;
}
/*
7 400000
0 1
0 2
1 3
1 4
2 5
2 6
*/
