#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int st[150][150];
int pitaj(int i, int j)
{
if(st[i][j]!=-1) return st[i][j];
st[i][j]=getDistance(i, j);
st[j][i]=st[i][j];
return st[i][j];
}
int par[150], db[150];
int brk[150];
vector<int> vr1, vr2;
int hubDistance(int N, int sub)
{
for(int i=0; i<150; i++) {par[i]=i; db[i]=1; brk[i]=1;}
vr1.resize(0);
vr2.resize(0);
int n=N;
memset(st, -1, sizeof(st));
for(int i=0; i<n; i++) st[i][i]=0;
int v1=0;
for(int i=1; i<n; i++)
{
if(pitaj(0, i)>pitaj(0, v1)) v1=i;
}
int v2=0;
for(int i=0; i<n; i++)
{
if(pitaj(v1, i)>pitaj(v1, v2)) v2=i;
}
int R=1e9, bro=0;
int d1;
int d2;
for(int i=0; i<n; i++)
{
if(i==v1 || i==v2) continue;
int t1=pitaj(i, v1);
int t2=pitaj(i, v2);
int t3=pitaj(v1, v2);
int r1=(t1+t3-t2)/2, r2=(t2+t3-t1)/2;
if(max(r1, r2)<R)
{
R=max(r1, r2);
bro=1;
d1=r1;
}
else if(max(r1, r2)==R)
{
bro=2;
d2=r1;
}
}
if(bro>1 && d1>d2) swap(d1, d2);
int br1=0, br2=0;
for(int i=0; i<n; i++)
{
int t1=pitaj(i, v1);
int t2=pitaj(i, v2);
int t3=pitaj(v1, v2);
int r1=(t1+t3-t2)/2;
if(r1==d1) vr1.push_back(i);
if(bro>1 && r1==d2) vr2.push_back(i);
if(r1<=d1) br1++;
else br2++;
}
if(br1<=N/2 && br2<=N/2) return R;
if(br1<=N/2)
{
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
int t1=pitaj(i, v1);
int t2=pitaj(i, v2);
int t3=pitaj(v1, v2);
int tr11=(t1+t3-t2)/2;
int s1=pitaj(j, v1);
int s2=pitaj(j, v2);
int s3=pitaj(v1, v2);
int ts11=(s1+s3-s2)/2;
int bt=pitaj(i, j);
if(((tr11<d2 && ts11<d2) || (tr11<d2 && ts11<d2))
|| (tr11==d2 && ts11==d2 && (t1+t2-t3)/2+(s1+s2-s3)/2!=bt))
{
int i2=i, j2=j;
while(i2!=par[i2]) i2=par[i2];
while(j2!=par[j2]) j2=par[j2];
if(i2==j2) continue;
if(db[i2]>db[j2])
{
par[j2]=i2;
brk[i2]+=brk[j2];
if(brk[i2]>n/2) return -R;
}
else if(db[i2]<db[j2])
{
par[i2]=j2;
brk[j2]+=brk[i2];
if(brk[j2]>n/2) return -R;
}
else
{
par[j2]=i2;
db[i2]++;
brk[i2]+=brk[j2];
if(brk[i2]>n/2) return -R;
}
}
}
}
return R;
}
else
{
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
int t1=pitaj(i, v1);
int t2=pitaj(i, v2);
int t3=pitaj(v1, v2);
int tr11=(t1+t3-t2)/2;
int s1=pitaj(j, v1);
int s2=pitaj(j, v2);
int s3=pitaj(v1, v2);
int ts11=(s1+s3-s2)/2;
int bt=pitaj(i, j);
if(((tr11<d1 && ts11<d1) || (tr11<d1 && ts11<d1))
|| (tr11==d1 && ts11==d1 && (t1+t2-t3)/2+(s1+s2-s3)/2!=bt))
{
int i2=i, j2=j;
while(i2!=par[i2]) i2=par[i2];
while(j2!=par[j2]) j2=par[j2];
if(i2==j2) continue;
if(db[i2]>db[j2])
{
par[j2]=i2;
brk[i2]+=brk[j2];
if(brk[i2]>n/2) return -R;
}
else if(db[i2]<db[j2])
{
par[i2]=j2;
brk[j2]+=brk[i2];
if(brk[j2]>n/2) return -R;
}
else
{
par[j2]=i2;
db[i2]++;
brk[i2]+=brk[j2];
if(brk[i2]>n/2) return -R;
}
}
}
}
return R;
}
return R;
}
