#include<bits/stdc++.h>
#include "fun.h"
using namespace std;
const int INF = 1e9;
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
int n;
namespace sub1{
vector<int>solve(){
vector<vector<int>>d(n, vector<int>(n));
for(int i = 0; i < n; i++){
d[i][i] = 0;
for(int j = i + 1; j < n; j++){
d[i][j] = d[j][i] = hoursRequired(i, j);
}
}
vector<vector<int>>dp(1 << n, vector<int>(n, -INF)), to(1 << n, vector<int>(n));
for(int mask = 1; mask < (1 << n); mask++){
vector<int>p;
for(int i = 0; i < n; i++){
if(1 << i & mask){
p.emplace_back(i);
}
}
if(p.size() == 1){
dp[mask][p[0]] = INF;
continue;
}
for(int& i : p){
for(int& j : p){
if(i != j && d[i][j] <= dp[mask ^ (1 << i)][j] && maximize(dp[mask][i], d[i][j])){
to[mask][i] = j;
}
}
}
}
vector<int>ans;
int state = (1 << n) - 1, i = -1;
for(i = 0; i < n; i++){
if(dp[state][i] > -1){
break;
}
}
for(int _ = 1; _ < n; _++){
ans.emplace_back(i);
int I = to[state][i];
state ^= 1 << i;
i = I;
}
ans.emplace_back(i);
reverse(ans.begin(), ans.end());
return ans;
}
}
namespace sub2{
vector<int>solve(){
vector<vector<int>>g(n);
vector<bool>vis(n, false);
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(hoursRequired(i, j) == 1){
g[i].emplace_back(j);
g[j].emplace_back(i);
}
}
}
function<pair<int, int>(int, int, int)>dfs;
dfs = [&] (int s, int p, int h){
pair<int, int>ret = make_pair(h, s);
for(int& d : g[s]){
if(d != p && !vis[d]){
maximize(ret, dfs(d, s, h + 1));
}
}
return ret;
};
int u = dfs(0, -1, 0).second;
vector<int>ans = {u};
for(int _ = 1; _ < n; _++){
vis[u] = true;
ans.emplace_back(u = dfs(u, -1, 0).second);
}
return ans;
}
}
namespace sub345{
vector<int>solve(){
int centroid = 0, opt_cnt = n;
for(int i = 1; i < n; i++){
int cnt = attractionsBehind(0, i);
if(cnt > (n >> 1) && minimize(opt_cnt, cnt)){
centroid = i;
}
}
vector<int>d(n), near;
for(int i = d[centroid] = 0; i < n; i++){
if(i != centroid && (d[i] = hoursRequired(centroid, i)) == 1){
near.emplace_back(i);
}
}
vector<vector<int>>part(near.size());
vector<int>color(n);
for(int i = 0; i < near.size(); i++){
part[color[near[i]] = i].emplace_back(near[i]);
}
for(int i = 0; i < n; i++){
if(i != centroid && find(near.begin(), near.end(), i) == near.end()){
bool flag = true;
for(int j = 0; j + 1 < near.size(); j++){
if(d[i] == hoursRequired(near[j], i) + 1){
flag = false;
part[color[i] = j].emplace_back(i);
break;
}
}
if(flag){
part.back().emplace_back(i);
color[i] = int(part.size()) - 1;
}
}
}
vector<int>ans;
for(int i = 0; i < part.size(); i++){
sort(part[i].begin(), part[i].end(), [&] (int x, int y){
return d[x] < d[y];
});
}
if(part.size() == 3){
int max_part, belong = 0;
for(int i = 1; i < 3; i++){
if(d[part[i].back()] > d[part[belong].back()]){
belong = i;
}
}
while(true){
if(((max_part = max({part[0].size(), part[1].size(), part[2].size()})) << 1) >= part[0].size() + part[1].size() + part[2].size()){
break;
}
int u = part[belong].back();
part[belong].pop_back();
ans.emplace_back(u);
int next_belong = -1;
for(int i = 0; i < 3; i++){
if(i != belong && !part[i].empty() && (next_belong == -1 || d[part[i].back()] > d[part[next_belong].back()])){
next_belong = i;
}
}
belong = next_belong;
}
for(int i = 0; i < 3; i++){
if(part[i].size() == max_part){
int l = (i == 0 ? 1 : 0), r = (i == 2 ? 1 : 2);
for(int& j : part[l]){
part[r].emplace_back(j);
}
sort(part[r].begin(), part[r].end(), [&] (int x, int y){
return d[x] < d[y];
});
part.erase(part.begin() + l);
break;
}
}
}
if(!part[0].empty() && !part[1].empty()){
int belong = int(d[part[0].back()] < d[part[1].back()]);
if(!ans.empty() && color[part[belong].back()] == color[ans.back()]){
belong ^= 1;
}
while(!part[belong].empty()){
ans.emplace_back(part[belong].back());
part[belong].pop_back();
belong ^= 1;
}
}
for(int i = 0; i < 2; i++){
while(!part[i].empty()){
ans.emplace_back(part[i].back());
part[i].pop_back();
}
}
ans.emplace_back(centroid);
return ans;
}
}
vector<int>createFunTour(int __n, int __q){
if((n = __n) <= 17){
return sub1::solve();
}
if(n <= 500){
return sub2::solve();
}
return sub345::solve();
}
