#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> distv;
int n;
int gd;
int dist(int a, int b){
if (a==b){return 0;}
if (a>b){
swap(a,b);
}
if (distv[a][b]!=-1){
return distv[a][b];
} else {
gd++;
assert(gd<=(n*(n-1))/2);
return distv[a][b]=getDistance(a,b);
}
}
int grab(){
int hd = 0;
int adist = -1;
int aind = -1;
for (int i = 0; i<n; i++){
int ds = dist(1,i);
if (adist<ds){
adist=ds;
aind=i;
}
}
int bdist = -1;
vector<int> bposs;
for (int i = 0; i<n; i++){
int ds = dist(aind,i);
if (bdist<ds){
bdist=ds;
bposs.clear();
bposs.push_back(i);
} else if (bdist==ds){
bposs.push_back(i);
}
}
int bind = bposs[0];
//for (int bind : bposs){
//cout<<"bind: "<<bind<<'\n';
bool exists = true;
//from adist to aind
//vector<int> diameter;
int hubdist = 1e9;
vector<int> hubposs;
for (int i = 0; i<n; i++){
if (i==aind||i==bind){continue;}
int distfroma = dist(aind,i)-(dist(aind,i)+dist(bind,i)-dist(aind,bind))/2;
int rv = max(distfroma,dist(aind,bind)-distfroma);
if (rv<hubdist){
hubdist=rv;
hubposs.clear();
hubposs.push_back(i);
} else if (rv==hubdist){
hubposs.push_back(i);
}
}
for (int hubind : hubposs){
//cout<<"hub: "<<hubind<<'\n';
hd=hubdist;
int hubfroma = dist(aind,hubind)-(dist(aind,hubind)+dist(bind,hubind)-dist(aind,bind))/2;;
vector<int> nodesinhub;
int befcnt=0;
int aftcnt=0;
for (int i = 0; i<n; i++){
int distfroma = dist(aind,i)-(dist(aind,i)+dist(bind,i)-dist(aind,bind))/2;
if (distfroma<hubfroma){
befcnt++;
} else if (distfroma==hubfroma){
nodesinhub.push_back(i);
} else {
aftcnt++;
}
}
//cout<<befcnt<<' '<<aftcnt<<' '<<nodesinhub.size()<<'\n';
if (befcnt>n/2||aftcnt>n/2){exists=false;continue;}
vector<bool> visited(n,false);
int nodesleft = nodesinhub.size();
for (int i : nodesinhub){
if (visited[i]){continue;}
if (nodesleft<=n/2){exists=true;break;}
int nodesingrp = 1;
visited[i]=true;
for (int j : nodesinhub){
if (!visited[j]){
if (dist(i,j)<dist(aind,i)+dist(aind,j)-2*hubfroma){
nodesingrp++;
visited[j]=true;
}
}
}
//cout<<nodesingrp<<'\n';
if (nodesingrp>n/2){exists=false;break;}
nodesleft-=nodesingrp;
}
if (exists){
return hd;
}
}
//}
return -hd;
}
int hubDistance(int N, int sub) {
gd=0;
n=N;
distv.assign(n,vector<int>(n,-1));
if (sub>2){return grab();}
int adist = -1;
int aind = -1;
for (int i = 0; i<n; i++){
int ds = dist(1,i);
if (adist<ds){
adist=ds;
aind=i;
}
}
int bdist = -1;
int bind = -1;
for (int i = 0; i<n; i++){
int ds = dist(aind,i);
if (bdist<ds){
bdist=ds;
bind=i;
}
}
//from adist to aind
//vector<int> diameter;
int hubdist = 1e9;
int hubind = -1;
for (int i = 0; i<n; i++){
if (i==aind||i==bind){continue;}
int distfroma = dist(aind,i)-(dist(aind,i)+dist(bind,i)-dist(aind,bind))/2;
int rv = max(distfroma,dist(aind,bind)-distfroma);
if (rv<hubdist){
hubdist=rv;
hubind=i;
}
}
return hubdist;
}
