#include "towns.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
map<pii,int> query_map;
int ask(int a, int b)
{
if(query_map.find({a,b}) != query_map.end()) return query_map[{a,b}];
int d = getDistance(a,b);
query_map[{a,b}] = d;
query_map[{b,a}] = d;
return d;
}
int dist1[110];
int dist2[110];
int dist3[110];
int V[110];
int hubDistance(int n, int sub)
{
query_map = {};
rep(i,n)
{
dist1[i] = 0;
dist2[i] = 0;
dist3[i] = 0;
}
rep2(i,1,n-1) dist1[i] = ask(0,i);
dist1[0] = 0;
int u = 0;
rep2(i,1,n-1)
{
if(dist1[i] > dist1[u]) u = i;
}
rep(i,n) if(i != u) dist2[i] = ask(u,i);
int max_dist = 0;
rep(i,n) max_dist = max(max_dist,dist2[i]);
rep(i,n) dist3[i] = (dist1[i] + dist2[i] - dist1[u])/2;
int R;
vi dists_u;
rep(i,n) dists_u.pb(dist2[i] - dist3[i]);
sort(all(dists_u));
int pop = 0;
vi hubs;
forall(it,dists_u)
{
if(it >= (max_dist+2)/2)
{
hubs.pb(pop);
hubs.pb(it);
break;
}
pop = it;
}
R = min(max(hubs[0],max_dist-hubs[0]),max(hubs[1],max_dist-hubs[1]));
int cnt0 = 0;
int cnt1 = 0;
rep(i,n)
{
if((dist2[i]-dist3[i]) <= hubs[0]) cnt0++;
else cnt1++;
}
int H = hubs[0];
if((cnt0 < cnt1 && max(hubs[1],max_dist-hubs[1]) == R) || max(hubs[0],max_dist-hubs[0]) != R) H = hubs[1];
vi bucket;
vi list;
rep(i,n)
{
V[i] = dist2[i] - dist3[i];
}
rep(i,n)
{
if(siz(list) == 0)
{
list.pb(i);
}
else
{
if((dist2[i] + dist2[list.back()] - 2*H != ask(i,list.back()) && V[i] == V[list.back()]) || (V[i] < H && V[list.back()] < H) || (V[i] > H && V[list.back()] > H))
{
bucket.pb(i);
}
else
{
list.pb(i);
if(siz(bucket) != 0)
{
list.pb(bucket.back());
bucket.pop_back();
}
}
}
}
int T = list.back();
list.pop_back();
bucket.pb(T);
while(!list.empty())
{
int T2 = list.back();
if((ask(T2,T) != dist2[T2] + dist2[T] - 2*H && V[T] == V[T2]) || (V[T] < H && V[T2] < H) || (V[T] > H && V[T2] > H))
{
if(siz(list) >= 2)
{
list.pop_back();
list.pop_back();
}
else
{
bucket.pb(list.back());
list.pop_back();
}
}
else
{
if(siz(bucket) == 0)
{
return R;
}
bucket.pop_back();
list.pop_back();
}
}
if(siz(bucket) > 0) return -R;
return R;
}
