#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]) {
pair<int, int> xx = deepest[a];
xx.first ++;
ans = max(ans, xx);
}
if (par[node] != -1 && !dead[par[node]]) {
pair<int, int> xx = furthest(par[node], node);
xx.first ++;
ans = max(ans, xx);
}
return ans;
}
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;
}
void dfs2(int node, int parent) {
par[node] = parent;
for (auto a : adj[node])
if (a != parent)
dfs2(a, node);
}
int root = 0;
int n, q;
std::vector<int> createFunTour(int N, int Q) {
n = N, q = Q;
if (n > 500) {
// we know it is a binary tree
// if 0 is connected to 1 and 2, use this solution
if (hoursRequired(0, 1) == 1 && hoursRequired(0, 2) == 1) {
root = 0;
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;
}
}
// otherwise build the tree
else {
// get distances to each node
vector<pair<bool, pair<int, int>>> spine;
spine.push_back({false, {0, 0}});
for (int i = 1; i < n; i ++) {
int dist = hoursRequired(0, i);
// bigger - attach it
while (spine.back().second.first > dist) {
if (spine.back().first == false) {
int a = spine.back().second.second, b = i;
// cout << a << " " << b << endl;
adj[a].push_back(b); adj[b].push_back(a);
}
spine.pop_back();
}
// equal - replace it
if (spine.back().second.first == dist) {
spine.pop_back();
}
bool attached = false;
// one smaller - attach it
if (spine.back().second.first == dist - 1) {
attached = true;
int a = spine.back().second.second, b = i;
// cout << a << " " << b << endl;
adj[a].push_back(b); adj[b].push_back(a);
}
spine.push_back({attached, {dist, i}});
}
root = spine.back().second.second;
dfs2(root, -1);
// for (int i = 0; i < n; i ++)
// cout << par[i] << " "; cout << endl;
}
memset(dead, false, sizeof(dead));
dfs1(root, -1);
pair<int, int> cur = deepest[root];
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;
}
// for (auto a : ans)
// cout << a << " "; cout << 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);
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
10 100000
0 1 1 2 1 3 3 4 4 5 3 6 6 8 7 8 8 9
*/
