#include <bits/stdc++.h>
using namespace std;
int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);
vector<int> createFunTour(int N, int Q) {
vector<int> siz(N);
for(int i = 0; i < N; i++) siz[i] = attractionsBehind(0, i);
auto comp = [&](int x, int y){ if((x * 2 > N) ^ (y * 2 > N)) return x > y; return x < y; };
const int cen = min_element(siz.begin(), siz.end(), comp) - siz.begin();
if(*max_element(siz.begin(), siz.end(), comp) * 2 == N){
const int cen1 = cen, cen2 = max_element(siz.begin(), siz.end(), comp) - siz.begin();
vector<int> dist1(N), dist2(N);
for(int i = 0; i < N; i++) dist1[i] = hoursRequired(cen1, i);
for(int i = 0; i < N; i++) dist2[i] = hoursRequired(cen2, i);
vector<int> a, b;
for(int i = 0; i < N; i++) (dist1[i] < dist2[i] ? a : b).push_back(i);
sort(a.begin(), a.end(), [&](int x, int y){ return dist1[x] > dist1[y]; });
sort(b.begin(), b.end(), [&](int x, int y){ return dist2[x] > dist2[y]; });
vector<int> ans;
for(int i = 0; i < N / 2; i++){
ans.push_back(a[i]);
ans.push_back(b[i]);
}
return ans;
}
vector<int> dist(N);
for(int i = 0; i < N; i++) dist[i] = hoursRequired(cen, i);
vector<int> dir;
for(int i = 0; i < N; i++) if(dist[i] == 1) dir.push_back(i);
vector<vector<int>> a(3);
for(int i = 0; i < N; i++) if(i != cen) for(int j = 0; j < 3; j++) if(j == 2 || hoursRequired(dir[j], i) < dist[i]){
a[j].push_back(i);
break;
}
for(auto& v : a) sort(v.begin(), v.end(), [&](int x, int y){ return dist[x] < dist[y]; });
sort(a.begin(), a.end(), [](auto& a, auto& b){ return a.size() > b.size(); });
int last = 0;
vector<int> ans = {a[0].back()};
a[0].pop_back();
while(a[0].size() || a[1].size() || a[2].size()){
bool flag = 0;
for(int i = 0; i < 3; i++) if(a[i].size() > a[(i + 1) % 3].size() + a[(i + 2) % 3].size()){
ans.push_back(a[i].back());
a[i].pop_back();
last = i;
flag = 1;
break;
}
if(flag) continue;
const int i = max((last + 1) % 3, (last + 2) % 3, [&](int x, int y) -> bool { if(a[y].empty()) return 0; if(a[x].empty()) return 1; return dist[a[x].back()] < dist[a[y].back()]; });
ans.push_back(a[i].back());
a[i].pop_back();
last = i;
}
ans.push_back(cen);
return ans;
}
