#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
int res1[100005], res2[100005], par[100005], depth[100005], n;
queue<pair<int, pair<int, int> > > q;
vector<pair<int, int> > des[100005];
vector<int> child[100005], vec, ans;
set<pair<int, int> > s[100005];
void dfs(int u)
{
s[u].insert({-depth[u], u});
for (int v:child[u])
{
depth[v]=depth[u]+1;
dfs(v);
s[u].insert(s[v].begin(), s[v].end());
}
}
vector<int> createFunTour(int nn, int qq)
{
n=nn;
int len=hoursRequired(0, n-1);
vec.push_back(0);
for (int i=1; i<=n-2; i++)
{
res1[i]=hoursRequired(0, i);
res2[i]=hoursRequired(i, n-1);
if (res1[i]+res2[i]==len)
vec.push_back(i);
else
des[res1[i]-(res1[i]+res2[i]-len)/2].push_back({(res1[i]+res2[i]-len)/2, i});
}
vec.push_back(n-1);
for (int i=0; i<=vec.size()-2; i++)
{
child[vec[i]].push_back(vec[i+1]);
par[vec[i+1]]=vec[i];
}
for (int i=0; i<vec.size(); i++)
{
sort(des[i].begin(), des[i].end());
int ind=0;
q.push({vec[i], {0, -1}});
q.push({vec[i], {0, n}});
while (!q.empty())
{
int u=q.front().first, v=q.front().second.first, w=q.front().second.second;
q.pop();
while (ind<des[i].size() && des[i][ind].first==v+1 && (des[i][ind].second-u)*(w-des[i][ind].second)>0)
{
child[u].push_back(des[i][ind].second);
par[des[i][ind].second]=u;
if (u<w)
{
q.push({des[i][ind].second, {v+1, u}});
q.push({des[i][ind].second, {v+1, w}});
}
else
{
q.push({des[i][ind].second, {v+1, w}});
q.push({des[i][ind].second, {v+1, u}});
}
ind++;
}
}
}
dfs(0);
int cur;
for (int i=0; i<n; i++)
{
if (child[i].empty())
{
cur=i;
break;
}
}
ans.push_back(cur);
{
int u=cur;
while (u)
{
s[u].erase({-depth[cur], cur});
u=par[u];
}
s[u].erase({-depth[cur], cur});
}
for (int i=1; i<n; i++)
{
int u=cur, cnt=1, mx=0, ind;
while (u)
{
cnt++;
int p=par[u];
for (int v:child[p])
{
if (v!=u && s[v].size() && mx<cnt-depth[v]-(*s[v].begin()).first)
{
mx=cnt-depth[v]-(*s[v].begin()).first;
ind=(*s[v].begin()).second;
}
}
u=p;
}
if (mx)
cur=ind;
else
cur=par[cur];
ans.push_back(cur);
{
int u=cur;
while (u)
{
s[u].erase({-depth[cur], cur});
u=par[u];
}
s[u].erase({-depth[cur], cur});
}
}
return ans;
}
