#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;
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];
}
}
int centroid(int x){
int mx=0;int y=x;
for(auto u:a[x])if(mx<s[u]){
mx=s[u];
y=u;
}
if(mx<=n/2)return x;
s[x]-=s[y];
s[y]=n;
return centroid(y);
}
pii bfs(int x){
pii arr;
queue<pi> pq;
vi vis(n,0);
vis[k]=1;
pq.push({1,x});
while(!pq.empty()){
int y=pq.front().F;
int z=pq.front().S;
pq.pop();
arr.PB({y,z});vis[z]=1;
for(auto u:a[z])if(vis[u]==0)pq.push({y+1,u});
}
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);
REP(i,0,n)REP(j,i+1,n)if(hoursRequired(i,j)==1){
a[i].PB(j);
a[j].PB(i);
}
dfs(0);
k=centroid(0);
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,3)arr[i]=bfs(a[k][i]);
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=pos;
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);
}
