#include "towns.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template <typename ...T> void qqbx(const char *s, T ...a) {
int cnt = sizeof...(T);
((std::cerr << "\e[1;32m(" << s << ") = ("), ..., (std::cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
std::cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L)
std::cerr << (f++ ? ", " : "") << *L;
std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)
using namespace std;
map<pair<int,int>,int> asked;
int ask(int a, int b) {
if (a == b) return 0;
if (a > b) swap(a, b);
if (asked.count({ a, b })) return asked[{ a, b }];
return asked[{ a, b }] = getDistance(a, b);
}
int hubDistance(int N, int sub) {
assert (1 <= sub && sub <= 6);
int A = 0, B = 0;
for (int i = 0; i < N; i++) {
if (ask(0, i) > ask(0, A)) {
A = i;
}
}
for (int i = 0; i < N; i++) {
if (ask(A, i) > ask(A, B)) {
B = i;
}
}
debug(A, B);
int R = ask(A, B);
for (int i = 0; i < N; i++) {
if (i == A || i == B) continue;
int AB = ask(A, B);
int AI = ask(A, i);
int BI = ask(B, i);
assert ((AB + abs(AI - BI)) % 2 == 0);
R = min(R, (AB + abs(AI - BI)) / 2);
}
debug(R);
return R;
}
