#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define ef emplace_front
#define fst first
#define snd second
const int INF = 1e9;
int furthest(int u, vb &used) {
const int N = sz(used);
int node = -1;
int maxi = -1;
forn(v, N) if (!used[v]) {
int curr = hoursRequired(u, v);
if (curr > maxi) {
maxi = curr;
node = v;
}
}
return node;
}
vi createFunTour(int N, int Q) {
if (N <= 500) {
vb used(N, false);
vi ret = {furthest(0, used)};
forn(i, N - 1) {
used[ret[i]] = true;
ret.pb(furthest(ret[i], used));
}
return ret;
}
bool flag = true;
forsn(i, 1, N) flag &= hoursRequired((i - 1) / 2, i) == 1;
vector<vi> adj(N);
vi par(N);
vii furthest(N);
auto dfs = [&](auto dfs, int i, int p) -> void {
furthest[i] = {0, i}, par[i] = p;
for (int j : adj[i]) if (j != p) {
dfs(dfs, j, i);
ii childBest = furthest[j];
childBest.fst++;
furthest[i] = max(furthest[i], childBest);
}
};
if (flag) {
forsn(i, 1, N) adj[(i - 1) / 2].pb(i);
dfs(dfs, 0, -1);
} else {
vi depth(N);
forn(i, N) depth[i] = hoursRequired(0, i);
par[0] = -1;
vector<tuple<bool, int, int>> st;
st.eb(false, 0, 0);
forsn(i, 1, N) {
while (true) {
auto [hasParent, node, dist] = st.back();
if (dist < depth[i]) break;
if (dist == depth[i] + 1 && !hasParent) {
adj[node].pb(i);
adj[i].pb(node);
}
st.pop_back();
}
auto [hasParent, node, dist] = st.back();
if (dist == depth[i] - 1) {
adj[i].pb(node);
adj[node].pb(i);
st.eb(true, i, depth[i]);
} else {
st.eb(false, i, depth[i]);
}
}
dfs(dfs, get<1>(st.back()), -1);
}
vb used(N, false);
auto find = [&](int x) {
ii maxi = furthest[x];
int up = 0;
while (par[x] != -1) {
int prev = x;
x = par[x], up++;
ii currBest = used[x] ? make_pair(-INF, x) : make_pair(0, x);
for (int y : adj[x]) if (y != par[x] && y != prev) {
ii childBest = furthest[y];
childBest.fst++;
currBest = max(currBest, childBest);
}
currBest.fst += up;
maxi = max(maxi, currBest);
}
return maxi;
};
auto deactivate = [&](int i) {
used[i] = true;
while (i != -1) {
if (used[i]) furthest[i] = {-INF, i};
else furthest[i] = {0, i};
for (int j : adj[i]) if (j != par[i]) {
ii childBest = furthest[j];
childBest.fst++;
furthest[i] = max(furthest[i], childBest);
}
i = par[i];
}
};
vi ret = {find(0).snd};
forn(i, N - 1) {
deactivate(ret[i]);
ret.pb(find(ret[i]).snd);
}
return ret;
}
