#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pf printf
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
int cnt;
map<int,int> memo[150];
inline int ask(int a,int b){
if(a==b)return 0;
if(memo[a].find(b)!=memo[a].end())return memo[a][b];
++cnt;
return memo[a][b]=memo[b][a]=getDistance(a,b);
}
int hubDistance(int N,int sub){
cnt=0;
for(int i=0;i<N;++i)memo[i].clear();
int a=0,b=0,diam=0;
for(int i=0;i<N;++i)if(ask(a,i)>ask(a,b))b=i;
for(int i=0;i<N;++i)diam=max(diam,ask(b,i));
int ans=diam;
vector<ii> v;
for(int i=0;i<N;++i){
int ab=ask(a,b),ai=ask(a,i),bi=ask(i,b);
int db=(ab+bi-ai)/2;
v.pb({db,i});
ans=min(ans,max(db,diam-db));
}
sort(all(v));
for(int i=0;i<N;++i){
if(max(v[i].fi,ask(a,b)-v[i].fi)!=ans)continue;
int l=i,r=i;
while(r<N-1&&v[r].fi==v[r+1].fi)++r;
if(l>N/2||N-r>N/2)continue;
vector<vi> cur,nxt,dead;
for(int i=l;i<=r;++i)cur.pb({v[i].se});
//pf("l: %d, r: %d\n",l,r);
vi rep={};
while(!cur.empty()){
/*
pf("cur: ");
for(vi x:cur){
pf("{");
for(int i:x)pf("%d ",i);
pf("} ");
}
pf("\n");
*/
for(int i=0;i<sz(cur);i+=2){
if(i+1==sz(cur)){
rep=cur[i];
}
else{
int x=cur[i][0],y=cur[i+1][0];
if(ask(b,x)+ask(b,y)-ask(x,y)>2*v[l].fi){
vi tmp;
for(int x:cur[i])tmp.pb(x);
for(int x:cur[i+1])tmp.pb(x);
nxt.pb(tmp);
}
else dead.pb(cur[i]),dead.pb(cur[i+1]);
}
}
swap(cur,nxt);
nxt.clear();
}
if(rep.empty())return ans;
int num=rep.size();
for(vi i:dead){
int x=rep[0],y=i[0];
if(ask(b,x)+ask(b,y)-ask(x,y)>2*v[l].fi)num+=i.size();
}
if(num<=N/2)return ans;
i=r;
assert(cnt<7*N/2);
}
return -ans;
}
