#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN];
vector<int> ans, big, small;
int dfs1(int node, int parent) {
int sz = 1;
for (auto a : adj[node])
if (a != parent)
sz += dfs1(a, node);
return sz;
}
void dfs2(int node, int parent, int depth, vector<pair<int, int>> &arr) {
arr.push_back({depth, node});
for (auto a : adj[node])
if (a != parent)
dfs2(a, node, depth + 1, arr);
}
void eradicate(int node) {
for (auto a : adj[node]) {
adj[a].erase(find(adj[a].begin(), adj[a].end(), node));
}
adj[node].clear();
}
std::vector<int> createFunTour(int N, int Q) {
int n = N, q = Q;
for (int i = 1; i < n; i ++) {
adj[i].push_back((i - 1) / 2);
adj[(i - 1) / 2].push_back(i);
}
int root = 0;
int rem = n;
while (rem) {
// no or only one child - done
if (adj[root].size() == 0) {
ans.push_back(root); break;
} else if (adj[root].size() == 1) {
ans.push_back(adj[root][0]);
ans.push_back(root); break;
}
// find big and small child
int big = 0, bigchild = -1;
for (auto a : adj[root]) {
int sz = dfs1(a, root);
if (sz > big) {
big = sz, bigchild = a;
}
}
int smallchild = adj[root][0];
if (bigchild == smallchild)
smallchild = adj[root][1];
vector<pair<int, int>> nodes_small, nodes_big;
dfs2(bigchild, root, 0, nodes_big);
dfs2(smallchild, root, 0, nodes_small);
sort(nodes_big.begin(), nodes_big.end());
sort(nodes_small.begin(), nodes_small.end());
bool bad = false;
while (nodes_small.size()) {
auto aa = nodes_small.back(); nodes_small.pop_back();
auto bb = nodes_big.back(); nodes_big.pop_back();
eradicate(aa.second); eradicate(bb.second);
ans.push_back(aa.second);
ans.push_back(bb.second);
if (bb.second == bigchild)
bad = true;
}
ans.push_back(root);
eradicate(root);
root = bigchild;
if (bad) break;
}
// 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
*/
