#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 , man;
int perp[MAXN] ;
int v[] = {0,0,0} ;
int d[MAXN][MAXN] ;
bool marc[MAXN][MAXN] ;
//
//union-find stuff
int pai[MAXN] , h[MAXN];
void init()
{
memset( v , 0 , sizeof v ) ;
lp(i,0,N) pai[i] = i ;
memset( h , 0 , sizeof h ) ;
memset(marc , 0 , sizeof marc ) ;
lp(i,0,N) marc[i][i] = 1 ;
}
int getDist( int x , int y )
{
if( marc[x][y] ) return d[x][y] ;
marc[x][y] = marc[y][x] = 1 ;
d[x][y] = d[y][x] = getDistance( x , y ) ;
return d[x][y] ;
}
void query( int x )
{ lp(i,0,N) d[x][i] = getDist( x, i ) ; }
int findMax( int x )
{ return max_element(d[x] , d[x] + N) - d[x] ; }
int findPerpendicular( int x )
{ return (d[A][x] + d[B][x] - d[A][B])/2 ; }
int findRadio()
{
int ans = inf ;
lp(i,0,N)
{
int k = max( d[A][i] , d[B][i] ) - perp[i] ;
int Man = d[A][i] > d[B][i] ? A : B ;
if( k < ans ) ans = k , man = Man ;
}
return ans ;
}
int checkPosition( int x )
{
int k = d[man][x] - perp[x] ;
if( k < R ) return 0 ;
if( k == R ) return 1 ;
return 2 ;
}
int sub4()
{
lp(i,0,N)
v[ checkPosition(i) ] ++ ;
lp(i,0,3)
if( v[i] > N/2 ) return -R ;
return R ;
}
bool check( vector<int> &vec )
{
if(vec.size() <= N/2) return 1 ;
int bucket = 0 , now = vec[0] ;
lp( i , 1 , vec.size() )
{
if( getDist( now , vec[i]) == perp[now] + perp[ vec[i] ] )
{
//different componentes
if( !bucket ) now = vec[i] , bucket = 1;
else bucket -- ;
}
bucket ++ ;
}
bucket = vec.size() ;
for(auto it : vec)
if( getDist(now , it) == perp[now] + perp[it] ) bucket -- ;
return (bucket <= N/2) ;
}
int hubDistance( int n , int sub)
{
N = n ;
init() ;
query(0) ;
A = findMax(0) ;
query(A) ;
B = findMax(A) ;
query(B) ;
lp(i,0,n) perp[i] = findPerpendicular(i) ;
R = findRadio() ;
if( sub < 3 ) return R ;
if( sub == 4 ) return sub4() ;
vector<int> s1 , s2 ;
bool balanced = 0 ;
lp(i,0,N)
if( checkPosition(i) == 1 ) s1.pb(i) ;
balanced |= check(s1) ;
int ori = R ;
R = d[A][B] - R ;
lp(i,0,N)
if( checkPosition(i) == 1 ) s2.pb(i) ;
balanced |= check(s2) ;
balanced = (balanced == 1) ? 1 : -1 ;
return ori * balanced ;
}
