////////////////////////////////
#include "fun.h"
//#include "grader.cpp"
////////////////////////////////
#include <bits/stdc++.h>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define pii pair<int, int>
using namespace std;
const int MAXN = (int)1e5 + 5;
const int MAXQ = (int)4e5 + 5;
vector <int> g[MAXN];
bool used[MAXN];
int dist[MAXN];
int n;
void calc(int v, int par, int len) {
dist[v] = len;
for (int to : g[v]) {
if (to == par) {
continue;
}
calc(to, v, len + 1);
}
}
int get_max() {
int pos = -1, mx = 0;
for (int i = 0; i < n; i++) {
if (!used[i] && dist[i] > mx) {
mx = dist[i];
pos = i;
}
}
return pos;
}
multiset <pii> st[MAXN];
void precalc(int v, int par) {
for (int to : g[v]) {
if (to == par) {
continue;
}
precalc(to, v);
for (pii el : st[to]) {
st[v].insert({el.first + 1, el.second});
}
}
st[v].insert({0, v});
}
void ers(int v) {
int cur = v;
int len = 0;
while (1) {
st[cur].erase(st[cur].find({len, v}));
if (cur == 0) {
break;
}
len++;
cur = (cur - 1) / 2;
}
}
vector <int> createFunTour(int N, int Q) {
n = N;
if (N <= 500) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (hoursRequired(i, j) == 1) {
g[i].pb(j);
g[j].pb(i);
}
}
}
int a = 1;
calc(a, -1, 0);
int b = get_max();
calc(b, -1, 0);
int c = get_max();
vector <int> ans = {b, c};
used[b] = used[c] = 1;
int used_cnt = 2;
int last = c;
while (used_cnt < n) {
calc(last, -1, 0);
int nxt = get_max();
last = nxt;
ans.pb(nxt);
used[last] = 1;
used_cnt++;
}
return ans;
}
else { // binary tree
for (int i = 1; i < N; i++) {
int x = i;
int y = (i - 1) / 2;
g[x].pb(y);
g[y].pb(x);
}
precalc(0, -1);
int a = 0;
calc(a, -1, 0);
int b = get_max();
calc(b, -1, 0);
int c = get_max();
vector <int> ans = {b, c};
ers(b);
ers(c);
int last = c;
while (szof(ans) < n) {
vector <pii> vec;
int cur = last;
int len = 0;
while (1) {
vec.pb({len, cur});
if (cur == 0) {
break;
}
cur = (cur - 1) / 2;
len++;
}
//cout << "wtf: " << last << endl;
//cout << "st: " << endl;
//for (int i = 0; i < n; i++) {
//cout << i << ": ";
//for (auto el : st[i]) {
//cout << el.fr << " " << el.sc << "|";
//}cout << endl;
//}
//cout << "vec: " << endl;
//for (auto el : vec) {
//cout << el.sc << " ";
//}cout << endl;
int best = -1, mx = -1;
if (!st[last].empty()) {
pii joop = *(--st[last].end());
best = joop.sc;
mx = joop.fr;
}
auto exist = [&](vector <pii> &vec, int vertex) {
for (auto el : vec) {
if (el.sc == vertex) {
return true;
}
}
return false;
};
//cout << "here" << endl;
for (auto el : vec) {
int v = el.sc;
int len = el.fr;
if (v == last) {
continue;
}
// parents
for (int to : g[v]) {
if (!exist(vec, to) && !st[to].empty()) {
pii joop = *(--st[to].end());
if (joop.fr + len > mx) {
mx = joop.fr + len;
best = joop.sc;
}
}
}
if (st[v].find({0, v}) != st[v].end()) {
if (len > mx) {
mx = len;
best = v;
}
}
}
ans.pb(best);
ers(best);
last = best;
}
//cout << "ans : " << endl;
//for (int el : ans) {
//cout << el << " ";
//}cout << endl;
return ans;
}
}
/*
7 400000
1 0
2 0
3 1
4 1
5 2
6 2
*/
