#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=120;
int n,cen,den;
int a[N],b[N],c[N],len[N];
int d[N][N];
bool was[N][N];
int Ask(int i, int j)
{
if(i==j) return 0;
if(!was[i][j]) d[i][j]=d[j][i]=getDistance(i,j);
was[i][j]=was[j][i]=1;
return d[i][j];
}
int hubDistance(int _N, int sub)
{
n=_N;cen=den=0;
for(int i=0;i<n;i++) for(int j=0;j<n;j++) was[i][j]=0;
for(int i=0;i<n;i++) a[i]=b[i]=c[i]=0;
for(int i=1;i<n;i++)
{
a[i]=Ask(0,i);
if(a[i]>a[cen]) cen=i;
}
for(int i=0;i<n;i++) if(i!=cen)
{
b[i]=Ask(cen,i);
if(b[i]>b[den]) den=i;
}
int diam=b[den],ans=diam,cnt=0,lo=1,hi=1,goal=diam/2;
for(int i=0;i<n;i++) if(i!=cen && i!=den)
{
c[i]=Ask(den,i);
int tmp=(c[i]+diam-b[i])/2;
//tmp=max(tmp,diam-tmp);
if(abs(ans-goal)>abs(tmp-goal)) ans=tmp,cnt=0;
if(ans==tmp) cnt++;
len[i]=(c[i]+b[i]-diam)/2;
}
vector<int> work;
for(int i=0;i<n;i++) if(i!=cen && i!=den)
{
int tmp=(c[i]+diam-b[i])/2;
if(tmp<ans) lo++;
if(tmp>ans) hi++;
if(tmp==ans) work.pb(i);
}
ans=max(ans,diam-ans);
if(sub<3) return ans;
if(sub==4)
{
if(lo>n/2 || hi>n/2 || cnt>n/2) return -ans;
return ans;
}
if(lo>n/2 || hi>n/2) return -ans;
while(work.size())
{
int sz=1,u=work.back();
work.pop_back();
vector<int> tmp;
for(int v:work)
{
if(Ask(u,v)==len[u]+len[v]) tmp.pb(v);
else sz++;
}
if(sz>n/2) return -ans;
work=tmp;
}
return ans;
}
