#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)
typedef pair<int,int>pi;
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
//----------------------
const int MX=1e5+10;
int N;
int C;
void find_centroid(){
vi sub(N);
FOR(i,0,N) sub[i]=attractionsBehind(0,i);
C=-1;
FOR(i,0,N) if(sub[i]>=(N+1)/2){
if(C==-1) C=i;
else if(sub[i]<sub[C]) C=i;
}
}
vi distC(MX);
vector<vi>subb;
vector<set<pi,greater<pi>>>sub;
void divide(){
FOR(i,0,N) distC[i]=hoursRequired(C,i);
FOR(i,0,N) if(distC[i]==1) subb.pb(vi{i});
assert(sz(subb)>=2);
vi vis(N,0);
FOR(i,0,2){
int c=subb[i][0];
vi dist(N);
FOR(j,0,N) dist[j]=hoursRequired(c,j);
FOR(j,0,N) if(j!=c && dist[j]==distC[j]-1) subb[i].pb(j);
for(int x: subb[i]) vis[x]=1;
}
vis[C]=1; if(sz(subb)>2) vis[subb[2][0]]=1;
FOR(i,0,N) if(!vis[i]) subb[2].pb(i);
FOR(i,0,sz(subb)){
set<pi,greater<pi>>s;
for(int u: subb[i]) s.insert({distC[u],u});
sub.pb(s);
}
}
vi ans;
void solve(){
int nb=sz(subb);
int u=C;
FOR(j,0,nb){
for(int i: subb[j]) if(distC[i]>distC[u]) u=i;
}
int merged=0;
while(1){
//merge if possible
for(int i=0; i<nb && !merged; i++){
int x=0;
FOR(j,0,nb) if(i!=j) x+=sz(sub[j]);
if(x<=sz(sub[i])){
int j=0; if(i==0) j++;
FOR(k,0,nb) if(k!=i && k!=j){
for(auto x: sub[k]) sub[j].insert(x);
sub[k].clear();
}
merged=1;
//careful
int prev=-1;
if(sz(ans)) prev=ans.back();
if(prev==-1) u=(*sub[i].begin()).se;
else{
if(distC[prev]>distC[u]) u=(*sub[i].begin()).se;
}
}
}
//erase the current one & move to the next
ans.pb(u);
int idx;
FOR(i,0,nb) if(sub[i].count({distC[u],u}))
sub[i].erase({distC[u],u}),idx=i;
int nxt=-1;
FOR(i,0,nb) if(i!=idx && sz(sub[i])){
int v=(*sub[i].begin()).se;
if(nxt==-1) nxt=v;
else if(distC[v]>distC[nxt]) nxt=v;
}
if(nxt==-1) break;
u=nxt;
}
ans.pb(C);
}
vi createFunTour(int N, int Q){
if(N==2) return vi{0,1};
::N=N;
find_centroid();
divide();
solve();
return ans;
}
/*
7 400000
0 1
0 5
0 6
1 2
1 4
2 3
*/
