//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});
}
}
// printf("\n\n%d containts: \n",v);
// printf("Left: ");
// for(auto x : dist_left[v])
// printf("(%d,%d) ",x.first,x.second);
// printf("\n\n");
// printf("right: ");
// for(auto x : dist_right[v])
// printf("(%d,%d) ",x.first,x.second);
// printf("\n\n");
}
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,0};
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 != 0)
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++;
// }
for(int i = N-1 ; i >= 0 ; i--)
ret.push_back(i);
return ret;
}
