#include<bits/stdc++.h>
using namespace std ;
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
const int N = 505 ;
const int Q = 4e5+5 ;
int arr[N][N] , par[N] , vis[N] , inv[N] ;
vector<tuple<int,int,int>> vt ;
vector<int> nei[N] ;
/*
int hoursRequired(int x , int y){
int dis[7][7]={{0,1,2,3,2,1,1},{1,0,1,2,1,2,2},{2,1,0,1,2,3,3},{3,2,1,0,3,4,4},{2,1,2,3,0,3,3},{1,2,3,4,3,0,2},{1,2,3,4,3,2,0}} ;
return dis[x][y] ;
};
*/
int hoursRequired(int x , int y) ;
int attractionsBehind(int x , int y) ;
int p(int k){
if(par[k]<0) return k ;
else return par[k]=p(par[k]) ;
}
void dfs(int node){
for(int i:nei[node]){
if(inv[i] || vis[i]!=-1) continue ;
vis[i]=vis[node]+1 ;
dfs(i) ;
}
}
vector<int> createFunTour(int n , int q){
for(int i=0 ; i<n ; i++){
for(int j=i+1 ; j<n ; j++){
arr[i][j]=arr[j][i]=hoursRequired(i,j) ;
vt.push_back({arr[i][j],i,j}) ;
}
}
sort(vt.begin(),vt.end()) ;
memset(par,-1,sizeof(par)) ;
for(int i=0 ; i<vt.size() ; i++){
int u = g1(vt[i]) , v = g2(vt[i]) , pu = p(u) , pv = p(v) ;
if(pu==pv) continue ;
nei[u].push_back(v) ;
nei[v].push_back(u) ;
if(par[pu]<=par[pv]) par[pu]+=par[pv] , par[pv]=pu ;
else par[pv]+=par[pu] , par[pu]=pv ;
}
int root ;
for(int i=0 ; i<n ; i++){
if(nei[i].size()==1){
root=i ;
break ;
}
}
vector<int> v ;
while(true){
v.push_back(root) ; inv[root]=1 ;
memset(vis,-1,sizeof(vis)) ;
vis[root]=0 ;
dfs(root) ;
int temp = *max_element(vis,vis+n) ;
if(temp==0) break ;
for(int i=0 ; i<n ; i++){
if(vis[i]==temp){
root=i ;
break ;
}
}
}
return v ;
}
/*
int main(){
vector<int> v = createFunTour(7, 400000) ;
for(int i:v) cout << i << ' ' ; cout << '\n' ;
return 0 ;
}
*/
