#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
/*
static int _N;
static int _dist[110][110];
static int _quota, _user_query;
void _ini_query(int N, int k) {
int ret;
_N = N;
for (int i = 0; i < _N; i++)
for (int j = 0; j < _N; j++) {
ret = scanf("%d", &_dist[i][j]);
assert(ret == 1);
}
if (k == 1 || k == 3) _quota = _N * (_N - 1) / 2;
else if (k == 2 || k == 4 || k == 6) _quota = (7 * _N + 1) / 2;
else _quota = 5 * _N;
_user_query = 0;
}
int getDistance(int i, int j) {
_user_query++;
if (_user_query > _quota) {
printf("0\n");
exit(0);
}
if (i < 0 || i >= _N) return 0;
if (j < 0 || j >= _N) return 0;
return _dist[i][j];
}
*/
map< pair<int,int>,int> seen;
int my_getDistance(int i,int j)
{
if(i==j)return 0;
if(seen.count({i,j}))return seen[{i,j}];
int d=getDistance(i,j);
seen[{i,j}]=d;
seen[{j,i}]=d;
return d;
}
int hubDistance(int n, int subtask)
{
seen={};
int u=1;
for(int i=2;i<n;i++)
{
if(my_getDistance(0,u)<my_getDistance(0,i))u=i;
}
int v=0;
for(int i=1;i<n;i++)
{
if(my_getDistance(u,v)<my_getDistance(u,i))v=i;
}
//cout<<"diameter "<<u<<" "<<v<<endl;
int outp=1e9;
for(int i=0;i<n;i++)
if(i!=u&&i!=v)
{
int cur=my_getDistance(u,v)+my_getDistance(i,u)-my_getDistance(i,v);
cur=cur/2;
outp=min(outp,max(cur,my_getDistance(v,u)-cur));
}
return outp;
}
/*
int main()
{
int ncase, R, N;
int subtask;
int ret;
ret = scanf("%d%d",&subtask,&ncase);
assert(ret == 2);
for (int i = 0; i < ncase; i++) {
ret = scanf("%d",&N);
assert(ret == 1);
_ini_query(N,subtask);
R=hubDistance(N,subtask);
printf("%d %d\n",R,_user_query);
}
}
*/
