#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN];
int par[MAXN];
pair<int, int> deepest[MAXN];
bool dead[MAXN];
// returns {fardepth, farnode}
pair<int, int> dfs1(int node, int parent) {
pair<int, int> ans = {0, node};
for (auto a : adj[node])
if (a != parent) {
pair<int, int> xx = dfs1(a, node);
xx.first ++;
ans = max(ans, xx);
}
deepest[node] = ans;
return ans;
}
pair<int, int> furthest(int node, int prev) {
pair<int, int> ans = {0, node};
for (auto a : adj[node])
if (a != prev && a != par[node])
ans = max(ans, deepest[a]);
if (par[node] != -1 && !dead[par[node]]) {
pair<int, int> xx = furthest(par[node], node);
xx.first ++;
ans = max(ans, xx);
}
return ans;
}
int root = 0;
void uproot(int node) {
pair<int, int> ans = {0, node};
for (auto a : adj[node])
if (a != par[node]) {
pair<int, int> xx = deepest[a];
xx.first ++;
ans = max(ans, xx);
}
deepest[node] = ans;
if (par[node] != -1 && !dead[par[node]])
uproot(par[node]);
}
void eradicate(int node) {
dead[node] = true;
for (auto a : adj[node]) {
adj[a].erase(find(adj[a].begin(), adj[a].end(), node));
}
adj[node].clear();
if (par[node] != -1 && !dead[par[node]])
uproot(par[node]);
}
void eradicate2(int node) {
for (auto a : adj[node]) {
adj[a].erase(find(adj[a].begin(), adj[a].end(), node));
}
adj[node].clear();
}
// returns {fardepth, farnode}
pair<int, int> furthest2(int node, int parent, int depth) {
pair<int, int> ans = {depth, node};
for (auto a : adj[node])
if (a != parent)
ans = max(ans, furthest2(a, node, depth + 1));
return ans;
}
std::vector<int> createFunTour(int N, int Q) {
int n = N, q = Q;
if (n > 500) {
// we know it is a binary tree
memset(dead, false, sizeof(dead));
par[0] = -1;
for (int i = 1; i < n; i ++) {
adj[i].push_back((i - 1) / 2);
adj[(i - 1) / 2].push_back(i);
par[i] = (i - 1) / 2;
}
dfs1(0, -1);
pair<int, int> cur = deepest[0];
vector<int> ans;
for (int tt = 0; tt < n - 1; tt ++) {
int prev = cur.second;
cur = furthest(prev, -1);
ans.push_back(prev);
eradicate(prev);
// cout << cur.first << " " << cur.second << endl;
}
ans.push_back(cur.second);
return ans;
} else {
for (int i = 0; i < n - 1; i ++) {
for (int j = i + 1; j < n; j ++) {
if (hoursRequired(i, j) == 1)
adj[i].push_back(j), adj[j].push_back(i);
}
}
// find any leaf node
pair<int, int> cur = {0, 0};
cur = furthest2(cur.second, -1, 0);
cur = furthest2(cur.second, -1, 0);
cur = furthest2(cur.second, -1, 0);
vector<int> ans;
for (int tt = 0; tt < n - 1; tt ++) {
int prev = cur.second;
cur = furthest2(prev, -1, 0);
ans.push_back(prev);
eradicate2(prev);
}
ans.push_back(cur.second);
// for (auto a : ans)
// cout << a << " "; cout << endl;
return ans;
}
}
/*
13 1000
0 1 0 2
1 3 1 4
2 5 2 6
3 7 3 8
4 9 4 10
5 11 5 12
*/
