#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), id(N, -1), up;
vector<vector<int>> v(3, vector<int>());
int cen = 0, best = N, bad = -1;
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) {
if(dis[x] != dis[y]) return dis[x] > dis[y];
else return (id[x] != bad) > (id[y] != bad);
};
rep(i, 0, N - 1) if(cen != i) {
dis[i] = hoursRequired(cen, i);
if(dis[i] == 1) up.push_back(i);
}
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), id[i] = 0;
else if(R + 1 == dis[i]) v[1].push_back(i), id[i] = 1;
else v[2].push_back(i), id[i] = 2;
}
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] ++]);
}
int ok = 0;
rep(i, 1, 2) if(v[i].size() - piv[i]
> v[ok].size() - piv[ok]) ok = i;
bad = pre;
rep(i, piv[ok], v[ok].size() - 1) L.push_back(v[ok][i]);
rep(j, 0, 2) if(j != ok)
rep(i, piv[j], v[j].size() - 1) R.push_back(v[j][i]);
sort(all(R), cmp);
if(dis[R[0]] > dis[L[0]] && id[R[0]] != pre) swap(L, R);
}
else L = v[0], R = v[1];
if(L.size() < R.size()) swap(L, R);
sort(all(R), cmp);
sort(all(L), cmp);
int l = 0, r = 0;
while(l < L.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;
}
