#include "fun.h"
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define ll long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 2000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
vector<int> createFunTour(int N, int Q) {
if(N == 2) return {0, 1};
vector<int> sz(N, 0), dis(N, 0), up;
vector<vector<int>> v(3, vector<int>());
int cen = 0, best = N;
rep(i, 1, N - 1) {
sz[i] = attractionsBehind(0, i);
if(sz[i] * 2 >= N && best > sz[i]) {
cen = i, best = sz[i];
}
}
auto cmp = [&](int x, int y) {
return dis[x] > dis[y];
};
rep(i, 0, N - 1) if(cen != i) {
dis[i] = hoursRequired(cen, i);
if(dis[i] == 1) up.push_back(i);
}
assert(up.size() == 2 || up.size() == 3);
rep(i, 0, N - 1) if(i != cen) {
int L = hoursRequired(up[0], i);
int R = hoursRequired(up[1], i);
if(L + 1 == dis[i]) v[0].push_back(i);
else if(R + 1 == dis[i]) v[1].push_back(i);
else v[2].push_back(i);
}
vector<int> L, R, ans;
if(up.size() == 3) {
vector<int> piv(3, 0);
int a = v[0].size(), b = v[1].size(), c = v[2].size();
rep(i, 0, 2) sort(all(v[i]), cmp);
int pre = -1, cur = 0, tot = 0;
while(max({a - piv[0], b - piv[1], c - piv[2]}) * 2 < a + b + c - tot) {
cur = -1;
rep(i, 0, 2) if(i != pre && piv[i] < v[i].size()) {
if(cur == -1 || dis[v[i][piv[i]]]
> dis[v[cur][piv[cur]]]) cur = i;
}
tot ++, pre = cur;
ans.push_back(v[cur][piv[cur] ++]);
}
rep(i, 1, 2) if(v[i].size() - piv[i]
> v[0].size() - piv[0]) swap(v[0], v[i]);
rep(i, piv[0], v[0].size() - 1) L.push_back(v[0][i]);
rep(i, piv[1], v[1].size() - 1) R.push_back(v[1][i]);
rep(i, piv[2], v[2].size() - 1) R.push_back(v[2][i]);
}
else L = v[0], R = v[1];
if(L.size() < R.size()) swap(L, R);
sort(all(R), cmp);
sort(all(L), cmp);
vprint(all(L));
vprint(all(R));
int l = 0, r = 0;
while(l < L.size() || r < R.size()) {
if(l < L.size()) ans.push_back(L[l++]);
if(r < R.size()) ans.push_back(R[r++]);
}
ans.push_back(cen);
return ans;
}
