#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a:b)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
const int MX = 115;
int n;
int mem[MX][MX];
int getD(int x, int y) {
if(mem[x][y] != -1) return mem[x][y];
return mem[x][y] = mem[y][x] = getDistance(x,y);
}
int hubDistance(int N, int sub) {
n = N;
RE(i,n) RE(j,n) mem[i][j] = -1;
RE(i,n) mem[i][i] = 0;
int x = 0, y = 0, z = 0, pathL = 0;
RE(i,n) {
int d = getD(x,i);
if(d > pathL) {
pathL = d;
y = i;
}
}
RE(i,n) {
int d = getD(y,i);
if(d > pathL) {
pathL = d;
z = i;
}
}
int best = 2*INF;
int ans = 0;
RE(i,n) {
if(i == x || i == y) continue;
int dx = getD(i,x);
int dy = getD(i,y);
int len = (dx+dy-getD(x,y))/2;
int dif = abs(pathL - len*2);
if(dif < best) {
best = dif;
ans = 0;
}
if(dif == best) {
ans = max(ans, dy-len);
ans = max(ans, dx-len);
}
}
return ans;
}
