#include "towns.h"
#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn=200,inf=1e9;
int dist[mxn+10][mxn+10],N;
int getdist(int a,int b){
if(b<a)swap(a,b);
if(a==b)return 0;
if(dist[a][b])return dist[a][b];
return dist[a][b]=getDistance(a,b);
}
void re(){
for(int i=0;i<N;i++)for(int j=0;j<N;j++)dist[i][j]=0;
}
namespace sub12{
int solve(){
re();
int ca=0,A=0,B=0;
for(int i=0;i<N;i++){
if(getdist(B,i)>ca){
ca=getdist(B,i);
A=i;
}
}
ca=0;
for(int i=0;i<N;i++){
if(getdist(A,i)>ca){
ca=getdist(A,i);
B=i;
}
}
int ans=inf;
for(int i=0;i<N;i++){
int x=(getdist(i,A)+getdist(i,B)-ca)/2;
ans=min(ans,max(getdist(i,A),getdist(i,B))-x);
}
return ans;
}
};
mt19937 rng(time(NULL));
namespace sub35{
int solve(){
re();
int ca=0,A=0,B=0;
for(int i=0;i<N;i++){
if(getdist(B,i)>ca){
ca=getdist(B,i);
A=i;
}
}
ca=0;
for(int i=0;i<N;i++){
if(getdist(A,i)>ca){
ca=getdist(A,i);
B=i;
}
}
int ans=inf;
int K;
vector<pii>v;
for(int i=0;i<N;i++){
int x=(getdist(i,A)+getdist(i,B)-ca)/2;
v.pb({i,getdist(i,A)-x});
ans=min(ans,max(getdist(i,A),getdist(i,B))-x);
}
int c1=0,c2=0;
vector<int>have;
for(int i=0;i<N;i++){
if(v[i].s<ans)c1++;
else if(v[i].s>ans)c2++;
else have.pb(i);
}
if(c1>(N/2)||c2>(N/2)){
have.clear();
c1=0,c2=0;
for(int i=0;i<N;i++){
if(v[i].s<ca-ans)c1++;
else if(v[i].s>ca-ans)c2++;
else have.pb(i);
}
}
if(c1>(N/2)||c2>(N/2))return -ans;
if(have.size()<=(N/2))return ans;
int cmx=have[0],c=1;
for(int i=1;i<have.size();i++){
if(getdist(have[i],cmx)==getdist(have[i],A)+getdist(cmx,B)-ca){
c--;
if(c<=0)c=1,cmx=have[i];
}
else c++;
}
int cnt=0;
for(int i=0;i<have.size();i++){
if(getdist(have[i],cmx)!=getdist(have[i],A)+getdist(cmx,B)-ca)cnt++;
}
if(cnt>(N/2))return -ans;
return ans;
}
};
namespace sub4{
int solve(){
re();
int ca=0,A=0,B=0;
for(int i=0;i<N;i++){
if(getdist(B,i)>ca){
ca=getdist(B,i);
A=i;
}
}
ca=0;
for(int i=0;i<N;i++){
if(getdist(A,i)>ca){
ca=getdist(A,i);
B=i;
}
}
int ans=inf;
int K;
vector<pii>v;
for(int i=0;i<N;i++){
int x=(getdist(i,A)+getdist(i,B)-ca)/2;
v.pb({i,getdist(i,A)-x});
ans=min(ans,max(getdist(i,A),getdist(i,B))-x);
}
int c1=0,c2=0;
vector<int>have;
for(int i=0;i<N;i++){
if(v[i].s<ans)c1++;
else if(v[i].s>ans)c2++;
else have.pb(i);
}
if(c1>(N/2)||c2>(N/2)){
have.clear();
c1=0,c2=0;
for(int i=0;i<N;i++){
if(v[i].s<ca-ans)c1++;
else if(v[i].s>ca-ans)c2++;
else have.pb(i);
}
}
if(c1>(N/2)||c2>(N/2)||have.size()>(N/2))return -ans;
return ans;
}
};
int hubDistance(int n, int sub){
N=n;
if(sub<=2)return sub12::solve();
if(sub==4)return sub4::solve();
return sub35::solve();
}
