#include <bits/stdc++.h>
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
using namespace std;
#include "towns.h"
/*
struct Interactive
{
int n,u,v,dis[202][202];
void Init()
{
cin>>n;
for(u=0;u<n;u++)
for(v=0;v<n;v++) cin>>dis[u][v];
}
} IR;
int getDistance(int u,int v)
{
cout<<u<<" "<<v<<'\n';
return IR.dis[u][v];
}
*/
int n,d[202][202],u,v,to_x[202],to_y[202];
vector <int> node[202];
int dis(int u,int v)
{
if(u==v) return 0;
if(u>v) swap(u,v);
if(d[u][v]>-1) return d[u][v];
return d[u][v]=getDistance(u,v);
}
int hubDistance(int n,int sub)
{
memset(d,-1,sizeof(d));
int x=-1,y=-1;
for(u=1;u<n;u++)
if(x==-1 || dis(0,x)<dis(0,u)) x=u;
for(u=0;u<n;u++)
if(y==-1 || dis(x,y)<dis(x,u)) y=u;
int mx_path=dis(x,y),res=1e9;
for(u=0;u<n;u++)
{
to_x[u]=(dis(u,x)+dis(0,x)-dis(0,u))/2;
to_y[u]=mx_path-to_x[u];
res=min(res,max(to_x[u],to_y[u]));
}
int okx=0,oky=0,nearx=0,neary=0;
vector <int> to_center,alive,dead;
for(u=0;u<n;u++)
{
if(max(to_x[u],to_y[u])==res)
{
okx|=(to_x[u]<=to_y[u]),oky|=(to_y[u]<to_x[u]);
to_center.push_back(u);
}
nearx+=(to_x[u]<=to_y[u]);
neary+=(to_y[u]<to_x[u]);
}
if(okx+oky==1)
{
alive=to_center;
if(okx==1 && (nearx-alive.size()>n/2 || neary>n/2)) return -res;
if(oky==1 && (neary-alive.size()>n/2 || nearx>n/2)) return -res;
}
else if(nearx==neary) return res;
else if(nearx>neary)
{
for(u=0;u<n;u++)
if(max(to_x[u],to_y[u])==res && (to_x[u]<=to_y[u]))
alive.push_back(u);
if(nearx-alive.size()>n/2) return -res;
}
else
{
for(u=0;u<n;u++)
if(max(to_x[u],to_y[u])==res && (to_y[u]<to_x[u]))
alive.push_back(u);
if(neary-alive.size()>n/2) return -res;
}
for(u=0;u<n;u++) node[u].clear(),node[u].push_back(u);
int last_odd=-1;
while(alive.size()>0)
{
vector <int> vec;
for(int i=0;i+1<alive.size();i+=2)
{
u=node[alive[i]][0];
v=node[alive[i+1]][0];
if(dis(x,u)+dis(x,v)-2*to_x[u]!=dis(u,v)) //Same part
{
vec.push_back(alive[i]);
for(int k:node[alive[i+1]]) node[alive[i]].push_back(k);
}
else dead.push_back(alive[i]),dead.push_back(alive[i+1]);
}
if(alive.size()%2==1)
{
if(last_odd>-1) dead.push_back(last_odd);
last_odd=alive.back();
}
alive=vec;
}
if(last_odd==-1) return res;
u=last_odd;
int cnt=node[u].size();
for(int v:dead)
if(dis(x,u)+dis(x,v)-2*to_x[u]!=dis(u,v)) cnt+=node[v].size();
if(cnt<=n/2) return res;
return -res;
}
/*
int main()
{
freopen("towns.inp","r",stdin);
freopen("towns.out","w",stdout);
IR.Init();
n=IR.n;
cout<<hubDistance(n,0);
}
*/
