#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<int,int> ii;
int n;
map<ii,int> M;
inline int query(int a, int b){
if(M.find(ii(a,b)) != M.end()) return M[ii(a,b)];
int res = getDistance(a,b);
M[ii(a,b)] = res;
M[ii(b,a)] = res;
return res;
}
struct thing{
int i, idis, adis;
};
int hubDistance(int N, int sub) {
M.clear();
n = N;
int A = 0;
int B = 1;
for(int i = 1;i < n;i++){
if(query(A, B) < query(A, i)) B = i;
}
map<int, vector<int> > paths;
vector<thing> stuff;
for(int i = 0;i < n;i++){
if(i == A or i == B) continue;
int idis = (query(i,A)+query(i,B)-query(A,B)) / 2;
int adis = query(i,A) - idis;
paths[adis].push_back(i);
stuff.push_back({i,idis,adis});
}
int ans = 102345678;
for(auto P : paths){
int adis = P.first, bdis = query(A,B) - adis;
int maxv = max(adis, bdis);
for(thing x : stuff){
maxv = max(maxv, x.idis + abs(x.adis-adis));
}
ans = min(ans, maxv);
}
return ans;
}
