#include "fun.h"
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int maxN = 1e5 + 5;
int n, isans[maxN];
int depth[maxN], choice[maxN], sz[4];
vector<int> List[4];
vector<int> Ans;
vector<int> createFunTour(int n, int Q) {
int u = 0, mini = n + 1;
REP(i, 0, n) {
int tmp = attractionsBehind(0, i);
if (tmp >= (n + 1) / 2 && tmp < mini) u = i, mini = tmp;
}
vector<int> all_next;
REP(i, 0, n) if (i != u) {
depth[i] = hoursRequired(u, i);
if (depth[i] == 1) {
all_next.push_back(i);
choice[i] = all_next.size();
}
}
REP(j, 0, (int)all_next.size() - 1) {
int node = all_next[j];
choice[node] = j + 1;
int tmp = sz[j + 1] = attractionsBehind(u, node);
REP(i, 0, n) if (!choice[i] && i != u) {
if (attractionsBehind(i, node) != tmp) choice[i] = j + 1;
}
}
REP(i, 0, n) if (!choice[i]) ++sz[all_next.size()], choice[i] = all_next.size();
{/// add root to smallest set
int id = 1;
FOR(i, 1, 3) if (sz[i] < sz[id]) id = i;
choice[u] = id;
++sz[id];
}
REP(i, 0, n) {
List[choice[i]].push_back(i);
}
FOR(i, 1, 3) {
depth[n] = -1;
List[i].push_back(n);
sort(List[i].begin(), List[i].end(), [] (int x, int y) { return depth[x] < depth[y]; });
}
/// solve
int type_now = 0;
int pre_depth = 0;
REP(step, 0, n) {
int type_next = 0;
if (sz[1] + sz[2] <= sz[3] && type_now != 3) {
if (type_now == 0) type_next = 3;
else if (pre_depth >= depth[List[type_now ^ 3].back()]) type_next = 3;
}
if (sz[1] + sz[3] <= sz[2] && type_now != 2) {
if (type_now == 0) type_next = 2;
else if (pre_depth >= depth[List[type_now ^ 2].back()]) type_next = 2;
}
if (sz[2] + sz[3] <= sz[1] && type_now != 1) {
if (type_now == 0) type_next = 1;
else if (pre_depth >= depth[List[type_now ^ 1].back()]) type_next = 1;
}
if (type_next == 0) {
int len_max = -1;
FOR(i, 1, 3) if (type_now != i && sz[i] && depth[List[i].back()] > len_max) {
type_next = i;
len_max = depth[List[i].back()];
}
}
pre_depth = depth[List[type_next].back()];
Ans.push_back(List[type_next].back());
List[type_next].pop_back();
--sz[type_next];
type_now = type_next;
}
return Ans;
}
