//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 155
#define pii pair<int, int>
#define ff first
#define ss second
#include "towns.h"
int n;
int save[maxn][maxn];
bool done[maxn][maxn];
int query(int u, int v) {
if (u == v || u >= n || v >= n) return 0;
if (done[u][v]) return save[u][v];
save[u][v] = save[v][u] = getDistance(u, v);
done[u][v] = done[v][u] = 1;
return save[u][v];
}
int hubDistance(int N, int sub) {
n = N;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) done[i][j] = 0;
}
vector<int> da, db, l(n), w(n), ws;
int b = 0, ma = 0;
for (int i = 0;i < n;i++) {
da.push_back(query(0, i));
if (da.back() > ma) {
ma = da.back();
b = i;
}
}
int len = ma;
for (int i = 0;i < n;i++) {
db.push_back(query(b, i));
ma = max(ma, db.back());
}
//debug(ma);
int R = 1<<30;
for (int i = 0;i < n;i++) {
l[i] = (da[i] + db[i] - len) / 2;
w[i] = db[i] - l[i];
//debug(l[i], w[i]);
ws.push_back(w[i]);
R = min(R, max(w[i], ma - w[i]));
}
return R;
/*
sort(ws.begin(), ws.end());
ws.resize(int(unique(ws.begin(), ws.end()) - ws.begin()));
int siz = ws.size();
vector<vector<int> > col(siz, vector<int>());
vector<int> pref(siz, 0), suf(siz, 0);
for (int i = 0;i < n;i++) {
int ind = lower_bound(ws.begin(), ws.end(), w[i]) - ws.begin();
col[ind].push_back(i);
}
for (int i = 0;i < siz;i++) pref[i] = col[i].size() + (i ? pref[i-1] : 0);
for (int i = siz-1;i >= 0;i--) suf[i] = col[i].size() + (i < siz-1 ? suf[i+1] : 0);
for (int i = 0;i < siz;i++) {
int v = max(w[i], ma - w[i]);
if (v == R) {
}
}
return R;
*/
}
