#include "towns.h"
#include <bits/stdc++.h>
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define ff first
#define ss second
#define pb push_back
#define pii pair<int,int>
#define MAXN 120
const int inf = 1e9 + 5 ;
using namespace std;
//
int N , A , B , R ;
int perp[MAXN] ;
int d[MAXN][MAXN] ;
bool marc[MAXN][MAXN] ;
map<int, vector<int> > g ;
//
void init()
{
memset( d , 0 , sizeof d ) ;
memset(marc , 0 , sizeof marc ) ;
lp(i,0,MAXN) marc[i][i] = 1 ;
R = inf ;
g.clear() ;
}
void ask( int x , int y )
{
if( marc[x][y] ) return ;
d[x][y] = d[y][x] = getDistance(x,y) ;
marc[x][y] = marc[y][x] = 1 ;
}
bool check( vector<int> &v )
{
if(v.size() <= N/2) return 1;
int candidat = v[0];
int cnt = 0;
for(auto it : v){
ask(it , candidat) ;
if(d[it][candidat] == perp[it] + perp[candidat])
{
if(!cnt) candidat = it, cnt = 1;
else --cnt;
}
else ++cnt;
}
cnt = v.size();
for(auto it : v){
ask(it , candidat) ;
if(d[candidat][it] == perp[candidat] + perp[it]) --cnt;
}
return (cnt <= N/2);
}
int hubDistance( int n , int sub)
{
N = n ;
vector<int> s ;
int balanced = 0 ;
init() ;
lp(i,0,n) ask(0,i) ;
A = max_element( d[0] , d[0]+n )- d[0] ;
lp(i,0,N) ask(A , i) ;
B = max_element( d[A] , d[A] + n ) - d[A] ;
lp(i,0,N) ask(B , i) ;
lp(i,0,n) perp[i] = ( d[A][i] + d[B][i] - d[A][B] ) / 2 ;
lp(i,0,n)
R = min( R , max( d[A][i] , d[B][i] ) - perp[i] ) ;
if( sub < 3 ) return R ;
for(int i=0; i<n; ++i)
{
int L = d[A][i] - perp[i] ;
g[L].pb(i);
}
if( sub == 4 )
{
int l = 0 , r = n;
for( auto &it : g )
{
r-= it.second.size() ;
if( max(it.first , d[A][B] - it.first) == R )
if( l <= N/2 and r <= N/2 and it.second.size() <= N/2 ) return R ;
l += it.second.size() ;
}
return -R ;
}
int cnt1 = 0, cnt2 = n;
for(auto &it : g)
{
cnt2 -= it.second.size();
if(max(it.first, d[A][B] - it.first) == R && cnt1 <= n/2 && cnt2 <= n/2)
balanced |= check(it.second);
cnt1 += it.second.size();
}
return R * ( balanced ? 1 : -1 ) ;
}
