#include "towns.h"
#include <bits/stdc++.h>
#include <random>
#include <utility>
using namespace std;
#ifndef LOCAL
#define cerr if(false) cerr
#endif
template< class T, class T2 > inline bool chkmax( T& a, const T2& b ){ return a < b ? a = b, 1 : 0 ; };
template< class T, class T2 > inline bool chkmin( T& a, const T2& b ){ return a > b ? a = b, 1 : 0 ; };
#define out(x) #x << " = " << x << " "
typedef long long ll;
const int MAX_N = 128;
const ll inf = 1e18;
int n;
std::map<std::pair< int, int >, ll > q;
ll makeQuery( int a, int b ){
//return getDistance( a, b );
if( a > b ) std::swap( a, b );
if( a == b ) return 0;
std::pair< int, int > curr = { a, b };
if( q.find( curr ) == q.end() ) q[curr] = getDistance( a, b );
return q[curr];
}
int hubDistance(int N, int sub) {
q.clear();
n = N;
ll mxDist = -1;
int d1, d2;
for( int i=0 ; i < n ; i++ ){
if( i == 0 ) continue;
ll currDist = makeQuery( 0, i );
if( chkmax( mxDist, currDist ) ) d1 = i;
}
mxDist = -1;
for( int i=0 ; i < n ; i++ ){
if( i == d1 ) continue;
ll currDist = makeQuery( d1, i );
if( chkmax( mxDist, currDist ) ) d2 = i;
}
ll distDiam = getDistance( d1, d2 );
//cerr << out( d1 ) << out( d2 ) << out( getDistance( d1, d2 ) ) << endl;
ll nas = inf;
for( int i=0 ; i < n ; i++ ){
if( i == d1 || i == d2 ) continue;
ll A = makeQuery( i, d1 );
ll B = distDiam;
ll C = makeQuery( d2, i );
//cerr << out( i ) << out( A ) << out( B ) << out( C ) << endl;
ll dist = ( A + B - C ) / 2LL;
ll currNas = std::max( dist, distDiam - dist );
chkmin( nas, currNas );
}
cerr << out( nas ) << endl;
return -nas;
}
