#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();
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 = -1;
vector<int> ans;
auto push = [&](int i){
ans.push_back(a[i].back());
a[i].pop_back();
last = i;
};
while(a[0].size() && a[1].size() && a[2].size()) [&]{
for(int i = 0; i < 3; i++) if(a[i].size() > a[(i + 1) % 3].size() + a[(i + 2) % 3].size()) return push(i);
if(ans.empty() || all_of(a.begin(), a.end(), [&](auto& v){ return dist[ans.back()] >= dist[v.back()]; })){
for(int i = 0; i < 3; i++) if(last != i && a[i].size() == a[(i + 1) % 3].size() + a[(i + 2) % 3].size()) return push(i);
}
const int i = max((last + 1) % 3, (last + 2) % 3, [&](int x, int y){ return dist[a[x].back()] < dist[a[y].back()]; });
push(i);
}();
while(a[0].size() || a[1].size() || a[2].size()){
const int i = [&](int x, int y){
if(a[x].empty()) return y;
if(a[y].empty()) return x;
if(dist[a[x].back()] < dist[a[y].back()]) return y;
return x;
}((last + 1) % 3, (last + 2) % 3);
push(i);
}
ans.push_back(cen);
return ans;
}
