#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 100010, MAX_D = 17;
int qdis(int a, int b) { return hoursRequired(a, b); }
int sbsz(int rt, int x) { return attractionsBehind(rt, x); }
// always go to the farthest point possible
// but it doesn't rely on deg(x) <= 3
std::vector<int> createFunTour(int N, int Q) {
int cen = -1, sz = N + 10;
for (int i = 0;i < N;++i) {
int q = sbsz(0, i);
if (q * 2 <= N) continue;
if (chmin(sz, q))
cen = i;
}
if (N == 2) return {0, 1};
vector<int> dis(N);
vector<int> nei;
for (int i = 0;i < N;++i) {
dis[i] = qdis(cen, i);
if (dis[i] == 1)
nei.pb(i);
}
vector<vector<pair<int,int>>> tree(nei.size());
for (int i = 0;i < N;++i) if (i != cen) {
for (int j = 0;j < nei.size();++j) {
if (j+1 == nei.size() || dis[i] == 1 + qdis(nei[j], i)) {
tree[j].pb(dis[i], i);
break;
}
}
}
for (auto &vec : tree) sort(AI(vec));
sort(AI(tree), [&](auto &a, auto &b) {
return a.size() < b.size();
});
vector<int> res;
int ts = N-1;
if (tree.size() == 3) {
int ind = -1;
for (int j = 0;j < 3;++j)
if (tree[j].size() * 2 >= ts) {
ind = j;
}
if (ind != -1) {
assert(ind > 0);
int os = tree[0].size();
tree[0].insert(end(tree[0]), AI(tree[3 - ind]));
inplace_merge(begin(tree[0]), begin(tree[0]) + os, end(tree[0]));
tree.erase(begin(tree) + 3 - ind);
}
}
sort(AI(tree), [&](auto &a, auto &b) {
return a.back() < b.back();
});
for (int t = 1;t < N;++t, --ts) {
if (tree.size() == 3) {
int ind = -1;
for (int j = 0;j < 3;++j)
if (tree[j].size() * 2 >= ts) {
ind = j;
break;
}
if (ind != -1) {
assert(ind > 0);
int os = tree[0].size();
tree[0].insert(end(tree[0]), AI(tree[3 - ind]));
inplace_merge(begin(tree[0]), begin(tree[0]) + os, end(tree[0]));
tree.erase(begin(tree) + 3 - ind);
}
}
if (tree.size() == 2)
assert(abs((int)tree[0].size() - (int)tree[1].size()) <= 1);
if (tree.size() == 3 && tree[2].back() > tree[1].back())
swap(tree[1], tree[2]);
if (tree[1].empty()) {
swap(tree[0], tree[1]);
assert(tree.size() == 2);
}
res.pb(tree[1].back().second);
tree[1].pop_back();
swap(tree[0], tree[1]);
}
res.pb(cen);
return res;
}
