#include "towns.h"
#include <bits/stdc++.h>
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define ff first
#define ss second
#define pb push_back
#define pii pair<int,int>
#define MAXN 120
const int inf = 1e9 + 5 ;
using namespace std;
//
int N , A , B , R ;
int perp[MAXN] ;
int d[MAXN][MAXN] ;
bool marc[MAXN][MAXN] ;
//
void init()
{
memset( d , 0 , sizeof d ) ;
memset(marc , 0 , sizeof marc ) ;
lp(i,0,MAXN) marc[i][i] = 1 ;
R = inf ;
}
void ask( int x , int y )
{
if( marc[x][y] ) return ;
d[x][y] = d[y][x] = getDistance(x,y) ;
marc[x][y] = marc[y][x] = 1 ;
}
bool check( vector<int> &s )
{
if( s.size() == 0 ) return 1 ;
int buck = 1 , ff = s[0] ;
lp(i,1,s.size())
{
int v = s[i] ;
ask(v,ff) ;
if(d[v][ff] == perp[i] + perp[v])
{
buck -- ;
if(buck == 0) buck = 1 , ff = v ;
}
else buck ++ ;
}
buck = s.size() ;
lp(i,0,N)
{
ask( ff , i ) ;
if( d[ff][i] == perp[i] + perp[ff] ) buck -- ;
}
return (buck <= N/2) ;
}
int hubDistance( int n , int sub)
{
N = n ;
vector<int> s ;
int balanced = 0 ;
init() ;
lp(i,0,n) ask(0,i) ;
A = max_element( d[0] , d[0]+n )- d[0] ;
lp(i,0,N) ask(A , i) ;
B = max_element( d[A] , d[A] + n ) - d[A] ;
lp(i,0,N) ask(B , i) ;
lp(i,0,n) perp[i] = ( d[A][i] + d[B][i] - d[A][B] ) / 2 ;
lp(i,0,n)
R = min( R , max( d[A][i] , d[B][i] ) - perp[i] ) ;
if( sub < 3 ) return R ;
lp(i,0,n)
if( d[A][i] - perp[i] == R )
s.pb(i) ;
balanced |= check(s) ;
s.resize(0) ;
lp(i,0,n)
if( d[B][i] - perp[i] == R )
s.pb(i) ;
balanced |= check(s) ;
return R * (balanced ? 1 : -1) ;
}
