#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int dydis = 1e5 + 10;
vector<int> gr[dydis];
int n;
bool rem[dydis] = {};
int dst[dydis] = {};
void dfs(int v, int came) {
if(rem[v]) return;
for(auto x : gr[v]) {
if(x == came) continue;
dst[x] = dst[v] + 1;
//cout << "dst[" << v << "] = " << dst[v] << ", tai dst[" << x << "] = " << dst[x] << endl;
dfs(x, v);
}
}
int furthest (int a) {
// cout << "ieskau atstumu nuo " << a << endl;
dst[a] = 0;
dfs(a, -1);
int mx = 0; int sk = a;
for(int i = 0; i < n; i++) {
if(rem[i]) continue;
// cout << "dst[" << i << "] = " << dst[i] << endl;
if(dst[i] > mx) {
mx = dst[i];
sk = i;
}
}
return sk;
}
vector<int> nMazas(){
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
if(hoursRequired(i, j) == 1) {
gr[i].push_back(j);
gr[j].push_back(i);
}
}
}
vector<int> ret;
int v = furthest(0);
for(int i = 0; i < n; i++) {
// cout << "i = " << i << ", v = " << v << endl;
ret.push_back(v);
int was = v;
v = furthest(v);
rem[was] = 1;
// cout << endl;
}
return ret;
}
pair<int, int> toliausia[dydis];
void d(int v, int came) {
if(rem[v]) return ;
toliausia[v] = {-1, v};
for(auto x : gr[v]) {
if(x == came) continue;
d(x, v);
toliausia[v] = max(toliausia[v], toliausia[x]);
}
toliausia[v].first++;
}
void remN(int v){
int in = v;
while(!rem[v]) {
toliausia[v] = {0, v};
if(v == in) toliausia[v] = {-1, -1};
for(auto x : gr[v]) {
if(x < v) continue;
toliausia[v] = max(toliausia[v], toliausia[x]);
}
if(v == 0) return ;
v = (v - 1) / 2;
}
rem[in] = 1;
/* cout << "isemus " << in << ", toliausios: \n";
for(int i = 0; i < n; i++) {
cout << i << "-ajai toliausia yra " << toliausia[i].second << endl;
}*/
}
int findFar(int v) {
pair<int, int> ret = toliausia[v];
int init = v;
int ds = 0;
while(true) {
for(auto x : gr[v]) {
if(x == init || x < v) continue;
ret = max(ret, make_pair(toliausia[x].first + ds, toliausia[x].second));
}
if(rem[v] || v == 0) break;
init = v;
v = (v - 1) / 2;
ds++;
}
return ret.second;
}
vector<int> createFunTour(int N, int Q) {
n = N;
// cout << "a" << endl;
// if(n <= 500) return nMazas();
for(int i = 1; i < n; i++) {
int pr = (i-1) / 2;
gr[pr].push_back(i);
gr[i].push_back(pr);
}
//cout << "x" << endl;
d(0, -1);
// cout << "don" << endl;
int v = toliausia[0].second;
set<int> nodes;
for(int i = 0; i < n; i++) nodes.insert(i);
vector<int> ret;
for(int i = 0; i < n-2; i++) {
int was = v;
v = findFar(v);
// cout << "toliausia nuo " << was << " yra " << v << endl;
remN(was);
ret.push_back(was);
nodes.erase(was);
}
ret.push_back(*nodes.begin());
nodes.erase(*nodes.begin());
ret.push_back(*nodes.begin());
// cout << "ret: "; for(auto x : ret) cout << x <<" "; cout << endl;
return ret;
}
