#include<bits/stdc++.h>
#include "towns.h"
using namespace std;
const int MAXN = 110;
int dist[MAXN][MAXN];
int hubDistance(int N, int sub)
{
if(sub <= 2)
{
int A = 0, B = 0;
for(int i = 1; i < N; i++)
{
dist[0][i] = dist[i][0] = getDistance(0, i);
if(dist[0][i] > dist[0][A]) A = i;
}
B = A;
for(int i = 0; i < N; i++)
{
if(i != 0 && i != A)
dist[A][i] = dist[i][A] = getDistance(A, i);
if(dist[A][i] > dist[A][B]) B = i;
}
if(B != 0)
for(int i = 1; i < N; i++)
if(i != A)
dist[B][i] = dist[i][B] = getDistance(B, i);
int d = dist[A][B], R = d;
for(int i = 0; i < N; i++)
{
if(i == A || i == B) continue;
int da = dist[A][B] + dist[A][i] - dist[i][B];
da /= 2;
R = min(R, max(da, d - da));
}
return R;
}
return 0;
}
