#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=115;
int memdist[maxn][maxn];
struct dsu{
vector<int>root;
vector<int>siz;
int mxsiz;
dsu(int n){
root=vector<int>(n);
iota(root.begin(),root.end(),0);
siz=vector<int>(n,1);
mxsiz=1;
}
int findRoot(int x){
if(x==root[x])
return x;
return root[x]=findRoot(root[x]);
}
bool unite(int x, int y){
x=findRoot(x);
y=findRoot(y);
if(x==y)
return 0;
if(siz[x]<siz[y])
swap(x,y);
siz[x]+=siz[y];
root[y]=x;
mxsiz=max(mxsiz,siz[x]);
return 1;
}
};
int cnt;
int dist(int a, int b){
if(memdist[a][b]!=-1){
return memdist[a][b];
}
assert(cnt--);
return memdist[a][b]=memdist[b][a]=getDistance(a,b);
}
int hubDistance(int n, int sub) {
cnt=(7*n)/2;
for(int i = 0;i<n;i++){
fill(memdist[i],memdist[i]+n,-1);
memdist[i][i]=0;
}
int dists[n];
for(int i = 0;i<n;i++){
dists[i]=dist(0,i);
}
int e1 = max_element(dists,dists+n)-dists;
for(int i = 0;i<n;i++){
dists[i]=dist(e1,i);
}
int e2 = max_element(dists,dists+n)-dists;
int diam = dists[e2];
int radius = 1e9;
map<int,vector<int>>group;
for(int i = 0;i<n;i++){
int d = dist(0,e1)+dist(e1,i)-dist(0,i);
d/=2;
group[d].push_back(i);
if(max(radius,diam-radius)>max(d,diam-d)){
radius=d;
}
}
int lef = 0;
for(int i = 0;i<radius;i++){
lef+=group[i].size();
}
int mid = group[radius].size();
int rig = n-lef-mid;
bool val1 = 1;
bool val2 = 1;
if(lef>n/2){
val1=0;
}
else if(rig>n/2){
val1=0;
}
else if(mid>n/2){
//gotta check
dsu ds(n);
vector<int>elems;
for(int i : group[radius]){
elems.push_back(i);
}
while(elems.size()>1){
vector<int>temp;
for(int i = 1;i<elems.size();i+=2){
int d = (dist(elems[i],elems[i-1]));
if(dist(e1,elems[i])+dist(e1,elems[i-1])-d==2*radius){
//seperate elems. ignore
}
else{
//same
ds.unite(elems[i],elems[i-1]);
temp.push_back(elems[i]);
}
}
elems=temp;
}
if(elems.size()){
//one left
set<int>s;
for(int i : group[radius]){
if(s.find(ds.findRoot(i))!=s.end()){
continue;
}
s.insert(ds.findRoot(i));
if(ds.findRoot(i)==ds.findRoot(elems[0]))
continue;
if(dist(e1,elems[0])+dist(e1,i)-dist(elems[0],i)==2*radius){
//do nothing
}
else{
ds.unite(elems[0],i);
}
}
}
if(ds.mxsiz>n/2){
val1=0;
}
}
if(val1){
return max(radius,diam-radius);
}
if((diam-radius!=radius)&&group[diam-radius].size()){
radius=diam-radius;
int lef = 0;
for(int i = 0;i<radius;i++){
lef+=group[i].size();
}
int mid = group[radius].size();
int rig = n-lef-mid;
if(lef>n/2){
val2=0;
}
else if(rig>n/2){
val2=0;
}
else if(mid>n/2){
//gotta check
dsu ds(n);
vector<int>elems;
for(int i : group[radius]){
elems.push_back(i);
}
while(elems.size()>1){
vector<int>temp;
for(int i = 1;i<elems.size();i+=2){
int d = dist(elems[i],elems[i-1]);
if(dist(e1,elems[i])+dist(e1,elems[i-1])-d==2*radius){
//seperate elems. ignore
}
else{
//same
ds.unite(elems[i],elems[i-1]);
temp.push_back(elems[i]);
}
}
elems=temp;
}
if(elems.size()){
//one left
set<int>s;
for(int i : group[radius]){
if(s.find(ds.findRoot(i))!=s.end())
continue;
s.insert(ds.findRoot(i));
if(ds.findRoot(i)==ds.findRoot(elems[0]))
continue;
if(dist(e1,elems[0])+dist(e1,i)-dist(elems[0],i)==2*radius){
//do nothing
}
else{
ds.unite(elems[0],i);
}
s.insert(ds.findRoot(i));
}
}
if(ds.mxsiz>n/2){
val2=0;
}
}
}
else{
val2=0;
}
if(val2){
return max(radius,diam-radius);
}
return -max(radius,diam-radius);
}
