#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
const int maxn=110;
map<pi,int> mem;
int query(int i, int j) {
if (mem[{i,j}]) {
return mem[{i,j}];
}
if (mem[{j,i}]) {
return mem[{j,i}];
}
if (i==j) {
return 0;
}
return mem[{i,j}]=getDistance(i,j);
}
int hubDistance(int n, int sub) {
/*for (int i=0; i<n; i++) {
dist[i][i]=0;
for (int j=i+1; j<n; j++) {
dist[i][j]=getDistance(i,j);
dist[j][i]=dist[i][j];
}
}
int ans=2e9;
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
map<int,int> dst;
for (int k=0; k<n; k++) {
if (k==i || k==j) {
continue;
}
dst[(dist[i][k]+dist[i][j]-dist[j][k])/2]=max(dst[(dist[i][k]+dist[i][j]-dist[j][k])/2],(dist[i][k]+dist[j][k]-dist[i][j])/2);
}
int val=0;
int prv=0;
map<int,int> nw;
for (auto pt=dst.begin(); pt!=dst.end(); pt++) {
val+=pt->fi-prv;
prv=pt->fi;
nw[pt->fi]=max(pt->se,val);
val=nw[pt->fi];
}
prv=dist[i][j];
val=0;
auto pt=dst.end();
do {
pt--;
val+=prv-pt->fi;
prv=pt->fi;
val=max(val,pt->se);
pt->se=max(val,nw[pt->fi]);
ans=min(ans,pt->se);
} while (pt!=dst.begin());
}
}
bool has=0;
for (int i=0; i<n && !has; i++) {
for (int j=i+1; j<n && !has; j++) {
map<int,int> dst;
map<int,vi> adj;
for (int k=0; k<n; k++) {
if (k==i || k==j) {
continue;
}
dst[(dist[i][k]+dist[i][j]-dist[j][k])/2]=max(dst[(dist[i][k]+dist[i][j]-dist[j][k])/2],(dist[i][k]+dist[j][k]-dist[i][j])/2);
adj[(dist[i][k]+dist[i][j]-dist[j][k])/2].pb(k);
}
int val=0;
int prv=0;
int sum=1;
map<int,int> nw;
map<int,int> cnts;
for (auto pt=dst.begin(); pt!=dst.end(); pt++) {
val+=pt->fi-prv;
prv=pt->fi;
nw[pt->fi]=max(pt->se,val);
val=nw[pt->fi];
cnts[pt->fi]=sum;
sum+=adj[pt->fi].size();
}
sum=1;
prv=dist[i][j];
val=0;
auto pt=dst.end();
do {
pt--;
val+=prv-pt->fi;
prv=pt->fi;
val=max(val,pt->se);
pt->se=max(val,nw[pt->fi]);
cnts[pt->fi]=max(sum,cnts[pt->fi]);
sum+=adj[pt->fi].size();
if (ans==pt->se) {
bool ok=1;
ok&=(cnts[pt->fi]<=n/2);
for (auto l:adj[pt->fi]) {
int tcnt=0;
for (auto m:adj[pt->fi]) {
if (dist[l][m]!=(dist[i][l]+dist[j][l]-dist[i][j])/2+(dist[i][m]+dist[j][m]-dist[i][j])/2) {
tcnt++;
}
}
ok&=tcnt<=n/2;
}
has|=ok;
}
} while (pt!=dst.begin());
}
}
return (has?ans:-ans);*/
mem.clear();
int i=1;
for (int k=0; k<n; k++) {
if (query(0,k)>query(0,i)) {
i=k;
}
}
int j=0;
for (int k=0; k<n; k++) {
if (query(i,k)>query(i,j)) {
j=k;
}
}
int ans=2e9;
vi fromi;
map<int,int> dst;
for (int k=0; k<n; k++) {
if (k==i || k==j) {
continue;
}
dst[(query(i,k)+query(i,j)-query(j,k))/2]=max(dst[(query(i,k)+query(i,j)-query(j,k))/2],(query(i,k)+query(j,k)-query(i,j))/2);
}
int val=0;
int prv=0;
map<int,int> nw;
for (auto pt=dst.begin(); pt!=dst.end(); pt++) {
val+=pt->fi-prv;
prv=pt->fi;
nw[pt->fi]=max(pt->se,val);
val=nw[pt->fi];
}
prv=query(i,j);
val=0;
auto pt=dst.end();
do {
pt--;
val+=prv-pt->fi;
prv=pt->fi;
val=max(val,pt->se);
pt->se=max(val,nw[pt->fi]);
if (pt->se<ans) {
ans=pt->se;
fromi.clear();
}
if (pt->se==ans) {
fromi.pb(pt->fi);
}
} while (pt!=dst.begin());
bool ok=0;
for (auto t:fromi) {
int a=0,b=0,c=0;
for (int k=0; k<n; k++) {
int dist=(query(i,j)+query(i,k)-query(j,k))/2;
if (dist<t) {
a++;
}
else if (dist==t) {
b++;
}
else {
c++;
}
}
if (max(max(a,b),c)<=n/2) {
ok=1;
break;
}
}
return (ok?ans:-ans);
}
