#include "fun.h"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, C;
int dist(int a, int b)
{
if (a == b) return 0;
return hoursRequired(a, b);
}
int subtree(int a, int b)
{
if (a == b) return N;
return attractionsBehind(a, b);
}
vi createFunTour(int n, int q)
{
N = n;
int sz[N], dC[N], d[2][N];
vi ans;
vpi guys[3];
int pos[N];
if (N <= 2)
{
ans.resize(N);
iota(ALL(ans), 0);
return ans;
}
vi pts;
//find the centroid. apparently this is the node with the smallest subtree size > N/2
FOR(i, 0, N)
{
sz[i] = subtree(0, i);
}
C = -1;
FOR(i, 0, N)
{
if (sz[i] < (N + 1)/2) continue;
if (C == -1 || sz[i] < sz[C]) C = i;
}
FOR(i, 0, N)
{
dC[i] = dist(C, i);
if (dC[i] == 1) pts.PB(i);
}
// for (int x : pts)
// {
// cerr << x << ' ';
// }
// cerr << endl;
FOR(i, 0, 2)
{
FOR(j, 0, N)
{
d[i][j] = dist(pts[i], j);
}
}
FOR(i, 0, N)
{
if (i == C) continue;
pos[i] = 2;
if (d[0][i] == dC[i] - 1) pos[i] = 0;
if (d[1][i] == dC[i] - 1) pos[i] = 1;
guys[pos[i]].PB({dC[i], i});
}
FOR(i, 0, 3)
{
sort(ALL(guys[i]));
}
int lst = -1;
FOR(i, 0, N - 1)
{
int guy = -1;
if (SZ(guys[0]) > SZ(guys[1]) + SZ(guys[2])) guy = 0;
else if (SZ(guys[1]) > SZ(guys[2]) + SZ(guys[0])) guy = 1;
else if (SZ(guys[2]) > SZ(guys[0]) + SZ(guys[1])) guy = 2;
else
{
FOR(i, 0, 3)
{
if (i == lst || guys[i].empty()) continue;
if (guy == -1 || guys[i].back().fi > guys[guy].back().fi) guy = i;
}
}
ans.PB(guys[guy].back().se);
guys[guy].pop_back();
assert(guy != lst);
lst = guy;
//find the farthest node.
}
ans.PB(C);
// for (int x : ans)
// {
// cerr << x << ' ';
// }
// cerr << endl;
return ans;
}
