//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "fun.h"
const int maxn = 1e5+10;
int n;
int val[maxn];
int dis[maxn];
vector <int> rt;
vector <pii> node[3];
vector <int> solve(vector<vector <pii> > nodee) {
vector <int> ans;
int cur = 0;
if (SZ(nodee[1])>SZ(nodee[0])) cur = 1;
while (!nodee[cur].empty()) {
ans.pb(nodee[cur].back().se);
nodee[cur].pop_back();
cur ^= 1;
}
return ans;
}
std::vector<int> createFunTour(int N, int Q) {
if (N==2) {
vector <int> tmp = {0,1};
return tmp;
}
int cent = -1;
n = N;
rep(i,0,n) {
val[i] = attractionsBehind(0,i);
if (val[i]*2>=N)
if (cent==-1 or val[i]<val[cent]) cent=i;
}
rep(i,0,n) if (cent!=i) {
dis[i] = hoursRequired(cent,i);
if (dis[i]==1) rt.pb(i);
}
rep(i,0,n) if (cent!=i) {
bool ok = false;
rep(j,0,SZ(rt)-1) if (hoursRequired(rt[j],i)+1==dis[i]) {
ok = true;
node[j].pb({dis[i],i});
break;
}
if (ok==false) node[SZ(rt)-1].pb({dis[i],i});
}
sort(ALL(node[0]));sort(ALL(node[1]));
vector <int> ans;
// debug(cent);
//for (auto it:node[1]) debug(it.se);
if (SZ(rt)==2) {
ans = solve({node[0],node[1]});
}
else {
sort(ALL(node[2]));
bool ok = false;
int lst,lstrt = -1;
rep(i,0,3) {
if (SZ(node[i])>=SZ(node[0])+SZ(node[1])+SZ(node[2]) - SZ(node[i])) {
vector <pii> small;
rep(j,0,3) if (i!=j) while (!node[j].empty()) small.pb(node[j].back()),node[j].pop_back();
sort(ALL(small));
vector <int> hmm = solve({small,node[i]});
for (auto it:hmm) ans.pb(it);
ok = true;
break;
}
}
if (ok==false) while (1) {
int tmp = -1;
if (lstrt!=0 and (tmp==-1 or node[1].back().fi > node[tmp].back().fi)) tmp = 0;
if (lstrt!=1 and (tmp==-1 or node[1].back().fi > node[tmp].back().fi)) tmp = 1;
if (lstrt!=2 and (tmp==-1 or node[2].back().fi > node[tmp].back().fi)) tmp = 2;
ans.pb(node[tmp].back().se);
lst = node[tmp].back().fi;
lstrt = tmp;
node[tmp].pop_back();
ok = false;
rep(i,0,3) {
if (SZ(node[i])==SZ(node[0])+SZ(node[1])+SZ(node[2]) - SZ(node[i])) {
vector <pii> small;
rep(j,0,3) if (i!=j) while (!node[j].empty()) small.pb(node[j].back()),node[j].pop_back();
sort(ALL(small));
if (small.back().fi>lst) {
ans.pb(small.back().se);
small.pop_back();
}
vector <int> hmm = solve({node[i],small});
for (auto it:hmm) ans.pb(it);
ok = true;
break;
}
}
if (ok) break;
}
}
ans.pb(cent);
return ans;
}
