#include "towns.h"
#include<iostream>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int MAX_N=2e2+2;
int diam;
int tov[MAX_N];
int tou[MAX_N];
int to0[MAX_N];
int ma[MAX_N][MAX_N];
int q;
int u,v,far;
set<int>nodes,nodes1,nodes2;
int n;
bool check(int a,int b)
{
if(a==u or a==v)while(1);
int dd;
if(a>b)swap(a,b);
if(a==0)dd=to0[b];
else
{
//if(q==n*(n-1)/2)while(1);
dd=getDistance(a,b);
q++;
}
if(tou[a]+tov[b]-diam==dd)return 0;
return 1;
}
int hubDistance(int N, int sub)
{
n=N;
for(int i=1;i<n;i++)
{
int cur=getDistance(u,i);
q++;
to0[i]=cur;
if(cur>far)
{
far=cur;
v=i;
}
}//0->v
diam=0;
for(int i=0;i<n;i++)
{
if(i==v)continue;
int cur;
if(i==0)cur=to0[v];
else {cur=getDistance(i,v);q++;}
tov[i]=cur;
if(cur>diam)
{
diam=cur;
u=i;
}
}//v->u
for(int i=0;i<n;i++)
{
if(i==u)continue;
if(i==0){tou[i]=to0[u];continue;}
if(i==v){tou[i]=tov[u];continue;}
tou[i]=getDistance(u,i);
q++;
}//u->all
int cntneg=1,cntpos=1,cntbaseneg=0,cntbasepos=0;
int mindif=1e9;
for(int i=0;i<n;i++)
{
if(i==u or i==v)continue;
int x=tou[i];
int y=tov[i];
int com=((x+y)-diam)/2;
x-=com;
y-=com;
int res=x-y;
mindif=min(mindif,abs(res));
}
for(int i=0;i<n;i++)
{
if(i==u or i==v)continue;
int x=tou[i];
int y=tov[i];
int com=((x+y)-diam)/2;
x-=com;
y-=com;
int res=x-y;
if(abs(res)==mindif)
{
if(res<=0){cntbaseneg++;nodes1.insert(i);}
else {cntbasepos++;nodes2.insert(i);}
}
else if(res<0)cntneg++;
else cntpos++;
}
int R=(diam-mindif)/2+mindif;
if(sub==4 or sub<=2)
{
if(cntbaseneg*cntbasepos!=0)
{
if(cntneg*2>n or (cntbasepos+cntpos)*2>n or cntbaseneg*2>n)return -R;
if(cntpos*2>n or (cntbaseneg+cntneg)*2>n or cntbasepos*2>n)return -R;
return R;
}
else
{
if(cntneg*2>n or cntpos*2>n or (cntbaseneg+cntbasepos)*2>n)return -R;
return R;
}
}
if(cntneg*2>n or cntpos*2>n)return -R;
if(cntbasepos*2<=n && cntbaseneg*2<=n)return R;
if(cntbaseneg*2>n)nodes=nodes1;
else nodes=nodes2;
while(nodes.size())
{
int cnt=1;
int uu=(*(nodes.begin()));
nodes.erase(uu);
if(nodes.size()==0)break;
set<int>::iterator it=nodes.begin();
set<int>dele;
while(it!=nodes.end())
{
if(check(uu,(*it)))
{
dele.insert((*it));
cnt++;
}
it++;
}
while(dele.size())
{
int el=(*(dele.begin()));
dele.erase(el);
nodes.erase(el);
}
//cout<<cnt<<"\n";
if(2*cnt>n)return -R;
}
return R;
}
