#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > adj(120, vector<int> (120, -1));
int gD(int i, int j){
if(i==j) return 0;
if(adj[i][j]==-1){
return adj[i][j] = adj[j][i] = getDistance(i, j);
}
return adj[i][j];
}
int hubDistance(int N, int sub) {
adj.assign(120, vector<int> (120, -1));
sub = sub*sub;
//cout<<"haaaahaaaaaaaHHZHEAHJAHAAAAAAA"<<endl;
int u=0, maxv = 0;
for(int i =1; i<N; i++){
if(gD(i, 0)>maxv){
u = i;
maxv = gD(i, 0);
}
}
maxv = 0;
int v = 0;
for(int i = 0; i<N; i++) if(i!=u){
if(gD(u, i)>maxv){
v = i;
maxv = gD(u, i);
}
}
//cout<<u<<" "<<v<<endl;
vector<int> diam(2e6+5, 0);
//int minimax = 1000000;
for(int i = 0; i<N; i++){
int x,y,z;
x = gD(u, v);
y = gD(u, i);
z = gD(v, i);
//cout<<i<<": "<<(x+y-z)/2<<endl;
diam[(x+y-z)/2]++;
}
int R = 10000000;
int Ri = 0;
/*for(int i = 0; i<30; i++){
cout<<diam[i]<<" ";
}
*/
//cout<<endl;
for(int i = 0; i<=gD(u,v); i++){
if(diam[i]>0&&R>max(i, gD(u,v)-i)){
R = max(i , gD(u,v)-i);
Ri = i;
//cout<<"i: "<<i<<" R: "<<R<<endl;
}
}
int boven = 0, onder = 0;
for(int i = 0; i<(int)diam.size(); i++){
if(i<Ri) onder+=diam[i];
if(i>Ri) boven+=diam[i];
}
//cout<<boven<<" "<<onder<<endl;
if(boven>N/2 || onder > N/2 || N-boven-onder>N/2) R = -R;
return R;
}
