#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 n , dis[N][N] , par[N] , vis1[N] ;
vector<tuple<int,int,int>> vt ;
vector<int> nei[N] , ans ;
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]) ;
}
int bfs(int node){
queue<int> q ;
int vis[N] ;
memset(vis,0,sizeof(vis)) ;
q.push(node) ; vis[node]=1 ;
while(!q.empty()){
int k = q.front() ; q.pop() ;
for(int i:nei[k]){
if(vis[i] || vis1[i]) continue ;
q.push(i) ; vis[i]=1 ;
}
if(q.empty()) return k ;
}
return -1 ;
}
vector<int> createFunTour(int n1 , int q){
n = n1 ;
for(int i=0 ; i<n ; i++){
for(int j=i+1 ; j<n ; j++) dis[i][j]=dis[j][i]=hoursRequired(i,j) , vt.push_back({dis[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 ;
if(par[pu]<=par[pv]) par[pu]+=par[pv] , par[pv]=pu ;
else par[pv]+=par[pu] , par[pu]=pv ;
nei[u].push_back(v) ; nei[v].push_back(u) ;
}
int node = bfs(bfs(1)) , cnt = n ;
while(cnt){
ans.push_back(node) ;
vis1[node]=1 ;
node=bfs(node) ;
cnt-- ;
}
return ans ;
}
