#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
int n;
int dist[maxn][maxn];
int query(int u, int v)
{
if( u == v || dist[u][v] != 0 )
return dist[u][v];
return dist[u][v] = dist[v][u] = getDistance(u, v);
}
int distPath(int a, int b, int c)
{
return (query(a, c) + query(b, c) - query(a, b))/2;
}
tuple<int,int> findDiameter()
{
int A = 0;
for(int i = 0 ; i < n ; i++)
if( query( 0 , A ) < query( 0 , i ) ) A = i;
int B = A;
for(int i = 0 ; i < n ; i++)
if( query( A , B ) < query( A , i ) ) B = i;
return { A , B };
}
tuple<int,int,int> getInfoCenter(int A, int B)
{
vector<int> leaves;
int R = query(A, B);
for(int i = 0 ; i < n ; i++)
{
int curR = distPath( 0 , i , A );
curR = max( curR , query(A, B) - curR );
if( curR < R )
leaves.clear();
if( curR <= R )
R = curR, leaves.push_back( i );
}
leaves.resize( 2 , -1 );
return { leaves[0] , leaves[1] , R };
}
int hubDistance(int N, int sub)
{
memset( dist , 0 , sizeof(dist) );
n = N;
auto [A, B] = findDiameter();
auto [C1, C2, R] = getInfoCenter(A, B);
return R;
}
