#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 remq;
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;
}
remq--;
return mem[{i,j}]=getDistance(i,j);
}
int hubDistance(int n, int sub) {
if (sub==5) {
remq=5*n;
}
else {
remq=(7*n+1)/2;
}
/*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;
vi bb;
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++;
bb.pb(k);
}
else {
c++;
}
}
if (max(max(a,b),c)<=n/2) {
ok=1;
break;
}
if (max(a,c)<=n/2) {
mt19937_64 rnd(42);
shuffle(all(bb),rnd);
while (remq) {
int l=bb.back();
bb.pop_back();
int tcnt=1;
for (int k=0; tcnt+bb.size()-k>n/2 && k<bb.size() && remq; k++) {
int m=bb[k];
if (query(l,m)!=(query(i,l)+query(j,l)-query(i,j))/2+(query(i,m)+query(j,m)-query(i,j))/2) {
tcnt++;
bb.erase(bb.begin()+k);
k--;
}
}
if (tcnt>n/2) {
break;
}
if (remq==0 || bb.size()<=n/2) {
ok=1;
break;
}
}
if (ok) {
break;
}
}
}
return (ok?ans:-ans);
}
