#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);
namespace k1r1t0 {
const int N = 110000;
bool used[N];
int n, d[N], ds[N][2];
vector<int> v[3];
vector<int> createFunTour(int N, int Q) {
n = N;
array<int, 2> mn = {n, 0};
for (int i = 1; i < n; i++) {
int sz = attractionsBehind(0, i);
if (2 * sz >= n) mn = min(mn, {sz, i});
}
int r = mn[1];
for (int i = 0; i < n; i++)
d[i] = hoursRequired(r, i);
vector<int> sub;
for (int i = 0; i < n; i++)
if (d[i] == 1)
sub.push_back(i);
int cnt = (int) sub.size();
for (int i = 0; i < cnt - 1; i++)
for (int j = 0; j < n; j++)
ds[j][i] = hoursRequired(sub[i], j);
for (int i = 0; i < n; i++) {
if (i == r) continue;
int t = cnt - 1;
for (int j = 0; j < cnt - 1; j++)
if (ds[i][j] + 1 == d[i])
t = j;
v[t].push_back(i);
}
if (cnt == 1)
return {0, 1};
int sm = 0;
for (int i = 1; i <= 2; i++)
if (v[sm].size() > v[i].size())
sm = i;
v[sm].push_back(r);
for (int k = 0; k < 3; k++)
sort(begin(v[k]), end(v[k]), [&](int i, int j) {return d[i] < d[j];});
random_shuffle(v, v + 3);
vector<int> ans;
int t = 0;
for (int i = 1; i <= 2; i++)
if (!v[i].empty() && (v[t].empty() || d[v[i].back()] > d[v[t].back()]))
t = i;
srand(time(NULL));
for (int i = 0; i < n; i++) {
int j = (t + 1) % 3;
int k = (t + 2) % 3;
int a = v[t].size();
int b = v[j].size();
int c = v[k].size();
if (b > c) {
swap(j, k);
swap(b, c);
}
if (a - 1 + b < c && b != 0) {
if (d[v[j].back()] > d[v[k].back()] && (v[t].size() == 1 || d[v[j].back()] > d[end(v[t])[-2]])) {
vector<int> na = v[j];
v[j].clear();
na.insert(na.end(), v[t].begin(), v[t].end());
v[t] = na;
ans.push_back(v[t].back());
v[t].pop_back();
sort(begin(v[t]), end(v[t]), [&](int i, int j) {return d[i] < d[j];});
} else {
vector<int> na = v[j];
v[j].clear();
na.insert(na.end(), v[t].begin(), v[t].end());
v[t] = na;
ans.push_back(v[t].back());
v[t].pop_back();
sort(begin(v[t]), end(v[t]), [&](int i, int j) {return d[i] < d[j];});
t = k;
}
} else {
ans.push_back(v[t].back());
v[t].pop_back();
if (v[j].empty() && v[k].empty())
continue;
if (v[j].empty()) t = k;
else if (v[k].empty()) t = j;
else {
if (d[v[j].back()] > d[v[k].back()]) t = j;
else t = k;
}
}
}
return ans;
}
};
vector<int> createFunTour(int N, int Q) {
return k1r1t0::createFunTour(N, Q);
}
