#include "towns.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
int n;
int hubDistance(int Ni, int sub){
n = Ni;
if(sub <= 2){
vector<int> dist_a(n), dist_b(n), dist_c(n);
int a, b, c;
a = 0;
int maximum_dist = -1, ind = -1;
for(int i=1;i<n;i++){
dist_a[i] = getDistance(a, i);
if(dist_a[i] > maximum_dist){
maximum_dist = dist_a[i];
ind = i;
}
}b = ind;
maximum_dist = -1;
for(int i=0;i<n;i++){
dist_b[i] = getDistance(b, i);
if(dist_b[i] > maximum_dist){
maximum_dist = dist_b[i];
ind = i;
}
}c = ind;
for(int i=0;i<n;i++){
dist_c[i] = getDistance(c,i);
}
int ans = 2e9;
for(int i=0;i<n;i++){
int d1 = (dist_b[i] + dist_c[i] - maximum_dist) / 2;
int t = max(dist_b[i] - d1, dist_c[i] - d1);
ans = min(ans, t);
}
return ans;
}return -12431223;
}
