//chockolateman
#include<bits/stdc++.h>
#include "fun.h"
using namespace std;
const int INF = 1e9;
int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);
int n,par[100005];
vector<int> adj[100005];
set<pair<int,int>> dist_left[100005];
set<pair<int,int>> dist_right[100005];
bool used[5005];
void dfs(int v,int p)
{
par[v] = p;
dist_left[v].insert({0,v});
dist_right[v].insert({0,v});
for(auto u : adj[v])
if(u != p)
{
dfs(u,v);
if(u == 2*v + 1)
{
for(auto x : dist_left[u])
dist_left[v].insert({x.first+1,x.second});
for(auto x : dist_right[u])
dist_left[v].insert({x.first+1,x.second});
}
else
{
for(auto x : dist_left[u])
dist_right[v].insert({x.first+1,x.second});
for(auto x : dist_right[u])
dist_right[v].insert({x.first+1,x.second});
}
}
}
pair<int,int> find_max_dist(int i)
{
pair<int,int> max_dist = {0,0};
if(!dist_left[i].empty())
max_dist = *dist_left[i].rbegin();
if(!dist_right[i].empty())
max_dist = max(max_dist,*dist_right[i].rbegin());
int extra = 0;
while(i != par[i])
{
extra++;
bool come_from_left = true;
int p = par[i];
if(i==2*p + 2)
come_from_left = false;
pair<int,int> cur_dist = {0,-1};
if(come_from_left)
{
if(!dist_right[p].empty())
cur_dist = *dist_right[p].rbegin();
}
else
{
if(!dist_left[p].empty())
cur_dist = *dist_left[p].rbegin();
}
// printf("For %d found %d %d\n",p,cur_dist.first,cur_dist.second);
if(cur_dist.second != -1)
cur_dist.first += extra;
max_dist = max(max_dist,cur_dist);
i = p;
}
return max_dist;
}
void remove_node(int v)
{
int cur_dist = 0;
dist_left[v].erase({0,v});
dist_right[v].erase({0,v});
int i = v;
while(i != par[i])
{
cur_dist++;
int p = par[i];
bool come_from_left = true;
if(i==2*p+2)
come_from_left = false;
if(come_from_left)
dist_left[p].erase({cur_dist,v});
else
dist_right[p].erase({cur_dist,v});
i = par[i];
}
}
stack<int> ans;
std::vector<int> createFunTour(int N, int Q)
{
n = N;
int H = hoursRequired(0, N - 1);
int A = attractionsBehind(0, N - 1);
vector<int> ret;
if(n <= 500)
{
for(int i = 0 ; i < N ; i++)
for(int j = i+1 ; j < N ; j++)
{
if(hoursRequired(i, j) == 1)
{
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
else
{
for(int i = 1 ; i < N ; i++)
{
par[i] = (i-1)/2;
adj[i].push_back(par[i]);
adj[par[i]].push_back(i);
}
}
dfs(0,0);
int i = N-1;
pair<int,int> new_dist = find_max_dist(i);
// printf("new_dist = %d %d\n",new_dist.first,new_dist.second);
int j = new_dist.second;
ret.push_back(i);
ret.push_back(j);
int prev = j;
remove_node(i);
remove_node(j);
int counter = 2;
while(counter < N)
{
new_dist = find_max_dist(prev);
int y = new_dist.second;
ret.push_back(y);
prev = y;
remove_node(y);
counter++;
}
return ret;
}
