#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
int SUB(int root,int x){return attractionsBehind(root,x);}
int DEP(int root,int x){return hoursRequired(root,x);}
const int N=100050;
/*int dep[N],sz[N];
int FindCentroid(int n){
pii mx={0,0};
for(int i=1;i<n;i++){
sz[i]=SUB(0,i);
dep[i]=DEP(0,i);
if(sz[i]*2>=n)mx=max(mx,{dep[i],i});
}
return mx.second;
}
int type[N],dist[N];*/
/*int sub[N],dep[N],side[N];
mt19937 rng(time(0));
vector<int> Solve(vector<int> nodes){
if(nodes.size()<=1)return nodes;
int n=nodes.size();
swap(nodes[0],nodes[rng()%n]);
int u=nodes[0];
printf("Solve %i: ",u);for(int i:nodes)printf("%i ",i);printf("\n");
vector<int> nxt;
for(int i:nodes){
if(i==u)dep[i]=0;
else dep[i]=DEP(u,i);
if(dep[i]==1)nxt.pb(i);
}
int v=nxt[rng()%nxt.size()];
for(int i:nodes){
if(i==u)side[i]=1;
else if(i==v)side[i]=2;
else side[i]=DEP(i,v)<dep[i]?2:1;
}
vector<pii> pts[2];
for(int i:nodes)pts[side[i]-1].pb({dep[i]-(side[i]==2),i});
sort(pts[0].rbegin(),pts[0].rend());
sort(pts[1].rbegin(),pts[1].rend());
if(pts[0].size()>pts[1].size())swap(pts[0],pts[1]);
vector<int> ans;
for(int i=0;i<pts[0].size();i++){
ans.pb(pts[1][i].second);
ans.pb(pts[0][i].second);
}
vector<int> o;
for(int i=pts[0].size();i<pts[1].size();i++)o.pb(pts[1][i].second);
vector<int> sol=Solve(o);
for(int i:sol)ans.pb(i);
return ans;
}*/
bool was[N];
int n;
int GetMx(int u){
int mx=0,best=-1;
for(int i=0;i<n;i++)if(!was[i]){
int d=DEP(u,i);
if(d>mx)mx=d,best=i;
}
return best;
}
vector<int> createFunTour(int n,int q){
::n=n;
int u=GetMx(0);
vector<int> ans;
while(1){
ans.pb(u);
was[u]=1;
u=GetMx(u);
if(u==-1)break;
}
return ans;
/*vector<int> nodes;
for(int i=0;i<n;i++)nodes.pb(i);
return Solve(nodes);*/
/*int cen=FindCentroid(n);
vector<int> f;
for(int i=0;i<n;i++){
dist[i]=DEP(cen,i);
if(dist[i]==1&&dep[i]==dep[cen]+1){
f.pb(i);
type[i]=f.size();
}
}
type[cen]=-1;
for(int j=0;j<f.size();j++){
for(int i=0;i<n;i++)if(!type[i]){
if(SUB(i,f[j])==n-sz[f[j]]+1)type[i]=j+1;
}
}
for(int i=0;i<n;i++)if(!type[i])type[i]=3;
priority_queue<pii> pq[3];
for(int i=0;i<n;i++)if(type[i]>0)pq[type[i]-1].push({dist[i],i});
vector<int> ans;
int ban=-1;
while(1){
int mx=0,sz=0,o=-1;
for(int i=0;i<3;i++)if(i!=ban){
if(pq[i].size()){
int now=pq[i].top().first;
if(now>mx||(now==mx&&sz<pq[i].size()))mx=now,sz=pq[i].size(),o=i;
}
}
if(o==-1)break;
ban=o;
ans.pb(pq[o].top().second);
pq[o].pop();
}
for(int i=0;i<3;i++)while(pq[i].size())ans.pb(pq[i].top().second),pq[i].pop();
ans.pb(cen);
return ans;*/
}
