#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(a,b,c) for(int a=b;a<c;a++)
#define PB push_back
#define F first
#define S second
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
vii a;
vi p,s,dist;
int n,k;
void dfs(int x){
for(auto u:a[x]){
if(u==p[x])continue;
p[u]=x;
dfs(u);
s[x]+=s[u];
}
}
pii bfs(int x){
pii arr;
arr.PB({1,x});
REP(i,0,n){
if(i==x||i==k)continue;
int y=hoursRequired(x,i);
int z=dist[i];
if(y>z)continue;
arr.PB({y+1,i});
}
sort(arr.begin(),arr.end());
return arr;
}
std::vector<int> createFunTour(int N, int q) {
n=N;
if(n==2)return {0,1};
a.resize(n);p.resize(n,-1);s.resize(n,1);
dfs(0);
vi cn(n,n);
k=0;
bool flag=0;
REP(i,1,n)cn[i]=attractionsBehind(0,i);
REP(i,1,n)if(cn[i]>n/2)flag=1;
if(flag)REP(i,1,n)if(cn[i]>n/2&&cn[i]<cn[k])k=i;
dist.resize(n);
REP(i,0,n)dist[i]=hoursRequired(k,i);
REP(i,0,n)if(dist[i]==1)a[k].PB(i);
int m=a[k].size();
if(m==2){
int c=a[k][0];
int d=a[k][1];
pii arr=bfs(c);
pii brr=bfs(d);
if(arr.size()<brr.size())swap(arr,brr);
vi ans;
while(!brr.empty()){
ans.PB(arr.back().S);
ans.PB(brr.back().S);
arr.pop_back();brr.pop_back();
}
if(!arr.empty())ans.PB(arr.back().S);
ans.PB(k);
return ans;
}
else{
vi ans;
vector<pii> arr(3);
REP(i,0,2)arr[i]=bfs(a[k][i]);
vi used(n,0);
used[k]=1;
REP(i,0,2)for(auto u:arr[i])used[u.S]=1;
REP(i,0,n)if(used[i]==0)arr[2].PB({dist[i],i});
sort(arr[2].begin(),arr[2].end());
if(arr[1].size()<arr[2].size())swap(arr[1],arr[2]);
if(arr[0].size()<arr[2].size())swap(arr[0],arr[2]);
vi sa(3);
REP(i,0,3)sa[i]=arr[i].size();
int pos=0;
REP(i,1,3)if(arr[pos].back().F<arr[i].back().F)pos=i;
int tmp=-1;
while(sa[0]!=sa[1]+sa[2]&&sa[1]!=sa[0]+sa[2]&&sa[2]!=sa[0]+sa[1]){
ans.PB(arr[pos].back().S);
arr[pos].pop_back();
sa[pos]--;
tmp=arr[pos].back().S;
int pos2=0;
if(pos==0)pos2++;
REP(i,0,3){
if(i==pos)continue;
if(arr[pos2].back().F<arr[i].back().F)pos2=i;
}
pos=pos2;
}
if(arr[1].size()<arr[2].size())swap(arr[1],arr[2]);
if(arr[0].size()<arr[2].size())swap(arr[0],arr[2]);
if(arr[0].size()<arr[1].size())swap(arr[0],arr[1]);
for(auto u:arr[2])arr[1].PB(u);
sort(arr[1].begin(),arr[1].end());
if(tmp==arr[0].back().S){
ans.PB(arr[1].back().S);
arr[1].pop_back();
}
while(!arr[1].empty()){
ans.PB(arr[0].back().S);
ans.PB(arr[1].back().S);
arr[0].pop_back();
arr[1].pop_back();
}
if(!arr[0].empty())ans.PB(arr[0].back().S);
ans.PB(k);
return ans;
}
// int A = attractionsBehind(0, n - 1);
return std::vector<int>(n);
}
