#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int dis[510][510], used[maxn], par[maxn], depth[maxn];
vector < int > g[maxn];
set < pair < int, int > > sub[maxn];
void dfs(int v)
{
sub[v].insert({depth[v], v});
for (int u : g[v])
{
depth[u] = depth[v] + 1;
par[u] = v;
dfs(u);
for (pair < int, int > nb : sub[u])
sub[v].insert(nb);
}
}
vector<int> createFunTour(int N, int Q)
{
if (N > 500)
{
for (int i = 1; i < N; i ++)
{
g[(i - 1) / 2].push_back(i);
}
par[0] = -1;
dfs(0);
int cur = N - 1;
vector < int > ans;
ans.push_back(cur);
for (int step = 1; step < N; step ++)
{
///cout << cur << endl;
int v = cur;
while(v != -1)
{
sub[v].erase({depth[cur], cur});
v = par[v];
}
int nxt = -1, dis = -10;
if (!sub[cur].empty())
{
nxt = sub[cur].rbegin() -> second;
dis = sub[cur].rbegin() -> first - depth[cur];
}
v = cur;
while(v != 0)
{
for (int child : g[par[v]])
{
if (child == v)
continue;
if (sub[child].size() == 0)
continue;
///cout << "here " << child << endl;
int len = sub[child].rbegin() -> first + depth[cur] - 2 * depth[par[v]];
///cout << len << " " << dis << endl;
if (len > dis)
{
dis = len;
nxt = sub[child].rbegin() -> second;
///cout << nxt << endl;
}
}
if (sub[par[v]].size() > sub[v].size())
{
if (depth[cur] - depth[par[v]] > dis)
{
dis = depth[cur] - depth[par[v]];
nxt = par[v];
}
}
v = par[v];
}
cur = nxt;
ans.push_back(cur);
}
// for (int v : ans)
// cout << v << " ";
// cout << endl;
return ans;
}
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++)
{
dis[i][j] = hoursRequired(i, j);
}
int cur = 0;
for (int i = 1; i < N; i ++)
if (dis[0][i] > dis[0][cur])
cur = i;
vector < int > ans;
ans.push_back(cur);
used[cur] = 1;
for (int i = 1; i < N; i ++)
{
int v = 1;
while(used[v] == 1)
v ++;
for (int j = 0; j < N; j ++)
{
if (used[j])
continue;
if (dis[cur][j] > dis[cur][v])
v = j;
}
ans.push_back(v);
used[v] = 1;
cur = v;
}
return ans;
}
