#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int>pii;
int dis[111][111];
int ch,n,maxi,maxj,maxx;
struct tri{
int a,b,c;
};
bool cmp(tri A, tri B){return A.a<B.a;}
vector<tri>X;
vector<int>V[111],D[111];
int H[111];
void f(int r)
{
if(ch==1)return ;
int cnt0=1,cnt1=1,cnt2=0;
for(auto &k:X)
{
if(k.a==r)cnt2++;
else if(k.a<r)cnt0++;
else cnt1++;
}
if(cnt0>n/2 || cnt1>n/2)return ;
if(cnt2<=n/2)
{
ch=1;
return ;
}
vector<pii>C;
for(auto &k:X)
{
if(k.a==r)C.push_back({k.b,k.c});
else if(k.a<r)C.push_back({r-k.a+k.b,k.c});
else C.push_back({k.a-r+k.b,k.c});
}
C.push_back({r,maxi});
C.push_back({maxx-r,maxj});
int siz=1;
for(int i=1;i<=n;i++)
{
V[i].clear();
D[i].clear();
}
for(auto &k:C)H[k.second]=k.first;
for(int i=0;i<n;i++)
{
if(V[siz].empty())V[siz].push_back(i);
else
{
if(!dis[V[siz][0]][i])dis[V[siz][0]][i]=dis[i][V[siz][0]]=getDistance(V[siz][0],i);
if(dis[V[siz][0]][i]==H[V[siz][0]]+H[i])D[siz].push_back(i);
else V[siz].push_back(i);
if(sz(V[siz])==sz(D[siz]))
{
siz++;
}
}
}/*
int o=0;
int candi=V[siz][0];
o+=sz(V[siz]);
for(int j=1;j<siz;j++)
{
if(!dis[V[j][0]][candi])dis[V[j][0]][candi]=dis[candi][V[j][0]]=getDistance(V[j][0],candi);
if(dis[V[j][0]][candi]==H[V[j][0]]+H[candi])
{
for(auto &k:D[j])
{
if(!dis[k][candi])dis[k][candi]=dis[candi][k]=getDistance(k,candi);
if(dis[k][candi]!=H[k]+H[candi])o++;
}
}
else
{
o+=sz(V[j]);
}
}
if(o<=n/2)ch=1;*/
}
int hubDistance(int N, int sub) {
int R=1e9;
if(sub!=2 && sub!=4){
maxi=-1,maxj=-1,maxx=-1;
n=N;
memset(dis,0,sizeof(dis));
for(int i=1;i<N;i++)
{
dis[0][i]=dis[i][0]=getDistance(0,i);
if(dis[0][i]>maxx)
{
maxx=dis[0][i];
maxi=i;
}
}
maxx=-1;
for(int i=0;i<N;i++)
{
if(i!=maxi)
{
if(!dis[maxi][i])dis[maxi][i]=dis[i][maxi]=getDistance(i,maxi);
if(dis[maxi][i]>maxx)
{
maxx=dis[maxi][i];
maxj=i;
}
}
}
X.clear();
for(int i=0;i<N;i++)
{
if(i!=maxi && i!=maxj)
{
if(!dis[maxj][i])dis[maxj][i]=dis[i][maxj]=getDistance(maxj,i);
X.push_back({(dis[maxi][i]-dis[maxj][i]+maxx)/2,(dis[maxi][i]+dis[maxj][i]-maxx)/2,i});
}
}
sort(X.begin(),X.end(),cmp);
for(auto &k:X)
{
R=min(R,max(maxx-k.a,k.a));
}
ch=-1;
f(R);
if(R!=maxx-R)f(maxx-R);
return ch*R;
}
else
{
maxi=-1,maxj=-1,maxx=-1;
R=1e9;
for(int i=1;i<N;i++)
{
dis[0][i]=dis[i][0]=getDistance(0,i);
if(dis[0][i]>maxx)
{
maxx=dis[0][i];
maxi=i;
}
}
maxx=-1;
for(int i=0;i<N;i++)
{
if(i!=maxi)
{
dis[maxi][i]=dis[i][maxi]=getDistance(maxi,i);
if(dis[maxi][i]>maxx)
{
maxx=dis[maxi][i];
maxj=i;
}
}
}
vector<int>Z;
for(int i=0;i<N;i++)
{
if(i!=maxi && i!=maxj)
{
dis[maxj][i]=dis[i][maxj]=getDistance(maxj,i);
Z.push_back((dis[maxi][i]-dis[maxj][i]+maxx)/2);
}
}
sort(Z.begin(),Z.end());
for(auto &k:Z)
{
R=min(R,max(maxx-k,k));
}
ch=-1;
int cnt[3];
for(int i=0;i<3;i++)cnt[i]=0;
cnt[0]=cnt[2]=1;
for(auto &k:Z)
{
if(k<R)cnt[0]++;
else if(k==R)cnt[1]++;
else cnt[2]++;
}
if(cnt[0]<=N/2 && cnt[1]<=N/2 && cnt[2]<=N/2)ch=1;
for(int i=0;i<3;i++)cnt[i]=0;
cnt[0]=cnt[2]=1;
for(auto &k:Z)
{
if(k<maxx-R)cnt[0]++;
else if(k==maxx-R)cnt[1]++;
else cnt[2]++;
}
if(cnt[0]<=N/2 && cnt[1]<=N/2 && cnt[2]<=N/2)ch=1;
return ch*R;
}
}
