#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 , inf = 1e9+10 ;
using namespace std ;
int n , v , s , t , r ;
int myRadio[MAXN] ;
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] ;
r = inf ;
lp(i,0,n)
{
myRadio[i] = ( d[v][s] + d[s][i] - d[v][i] ) >> 1 ;
r = min(r, max( myRadio[i] , d[s][t] - myRadio[i] ) ) ;
}
return r ;
}
