#include "towns.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int inf=1e9+7;
int hubDistance(int n, int sub){
int best=0, id=0;
for(int i=1;i<n;i++){
int at=getDistance(0,i);
if(at>best){
best=at;
id=i;
}
}
vector<int>d1(n), d2(n);
for(int i=0;i<n;i++) d1[i]=getDistance(id,i);
int f1=id, f2=0; best=0;
for(int i=0;i<n;i++){
if(d1[i]>best){
best=d1[i];
f2=i;
}
}
for(int i=0;i<n;i++) d2[i]=getDistance(f2,i);
int r=inf;
for(int i=0;i<n;i++){
int x=abs(d1[i]-d2[i])+best;
r=min(r,x/2);
}
auto solve4_1=[&](){
int e=1, m=0, d=1;
for(int i=0;i<n;i++){
if(i==f1||i==f2) continue;
int x=(d1[i]-d2[i])+best; x/=2;
if(x<r) e++;
if(x==r) m++;
if(x>r) d++;
}
if(max({e,m,d})<=(n/2)) return r;
return -r;
};
auto solve4_2=[&](){
int e=1, m=0, d=1;
for(int i=0;i<n;i++){
if(i==f1||i==f2) continue;
int x=(d2[i]-d1[i])+best; x/=2;
if(x<r) e++;
if(x==r) m++;
if(x>r) d++;
}
if(max({e,m,d})<=(n/2)) return r;
return -r;
};
if(sub==4) return max(solve4_1(),solve4_2());
vector<int>z(n);
for(int i=0;i<n;i++){
int x=(d1[i]-d2[i])+best; x/=2;
z[i]=d1[i]-x;
}
auto calc=[&](vector<int> v){
vector<pii>comp;
int tam=1;
for(int x : v){
bool flag=true;
for(pii &y : comp){
if(getDistance(y.fi,x)!=z[y.fi]+z[x]){
flag=false;
y.se++;
tam=max(tam,y.se);
break;
}
}
if(flag) comp.push_back({x,1});
}
return tam;
};
auto solve1=[&](){
int e=1, m=0, d=1;
vector<int>aux;
for(int i=0;i<n;i++){
if(i==f1||i==f2) continue;
int x=(d1[i]-d2[i])+best; x/=2;
if(x<r) e++;
if(x==r) m++, aux.push_back(i);
if(x>r) d++;
}
if(max(e,d)>(n/2)) return -r;
if(calc(aux)<=(n/2)) return r;
return -r;
};
auto solve2=[&](){
int e=1, m=0, d=1;
vector<int>aux;
for(int i=0;i<n;i++){
if(i==f1||i==f2) continue;
int x=(d2[i]-d1[i])+best; x/=2;
if(x<r) e++;
if(x==r) m++, aux.push_back(i);
if(x>r) d++;
}
if(max(e,d)>(n/2)) return -r;
if(calc(aux)<=(n/2)) return r;
return -r;
};
return max(solve1(),solve2());
}
