#include <bits/stdc++.h>
#include "towns.h"
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define sz size()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define tiii tuple<int,int,int>
#define mkt make_tuple
const int MAXN = 120 ;
using namespace std ;
int n , v , s , t ;
int d[MAXN][MAXN] ;
inline void ask(int i , int j)
{
if( d[i][j] == -1 )
d[i][j] = d[j][i] = getDistance(i,j) ;
}
int hubDistance(int N, int sub)
{
memset(d, -1, sizeof d ) ;
lp(i,0,N) d[i][i] =0 ;
n = N ;
lp(i,0,n) ask(0,i) ;
v = 0 ;
s = max_element( d[v] , d[v]+n ) - d[v] ;
lp(i,0,n) ask(s,i) ;
t = max_element( d[s] , d[s] + n ) - d[s] ;
int R = ( d[v][s] + d[s][t] - d[v][t] ) >> 1 ;
R = max(R , d[s][t] - R ) ;
lp(i,0,n)
{
int curDist = ( d[v][s] + d[s][i] - d[v][i] ) >> 1 ;
R = min(R , max(curDist, d[s][t] - curDist ) ) ;
}
return R ;
}
