#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 115;
const int INF = 1e9 + 36;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
int n, cache[lim][lim];
int ask(int i, int j){
if(i > j){
swap(i, j);
}
int& ans = cache[i][j];
if(ans == -1){
ans = getDistance(i, j);
}
return ans;
}
namespace sub1{
int solve(){
int a, b, diam = 0, ans = INF;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(maximize(diam, ask(i, j))){
a = i;
b = j;
}
}
}
for(int i = 0; i < n; i++){
minimize(ans, max(ask(i, a), ask(i, b)) - ((ask(i, a) + ask(i, b) - diam) >> 1));
}
return ans;
}
}
namespace sub2{
int solve(){
int a = 0, b, diam = 0, ans = INF;
for(int i = 1, best = 0; i < n; i++){
if(maximize(best, ask(0, i))){
a = i;
}
}
for(int i = 0; i < n; i++){
if(maximize(diam, ask(a, i))){
b = i;
}
}
for(int i = 0; i < n; i++){
minimize(ans, max(ask(i, a), ask(i, b)) - ((ask(i, a) + ask(i, b) - diam) >> 1));
}
return ans;
}
}
namespace sub345{
int solve(){
int u = 0, v, diam = 0, min_rad = INF;
for(int i = 1, best = 0; i < n; i++){
if(maximize(best, ask(0, i))){
u = i;
}
}
for(int i = 0; i < n; i++){
if(maximize(diam, ask(u, i))){
v = i;
}
}
auto cal_0x = [&] (int i){
return (ask(0, i) + ask(0, u) - ask(u, i)) >> 1;
};
auto cal_ix = [&] (int i){
return (ask(0, i) + ask(u, i) - ask(0, u)) >> 1;
};
auto cal_ux = [&] (int i){
return (ask(u, i) + ask(0, u) - ask(0, i)) >> 1;
};
for(int i = 0, rod_0 = (ask(0, u) + ask(0, v) - diam) >> 1; i < n; i++){
if(cal_0x(i) >= rod_0){
minimize(min_rad, max(cal_ux(i), diam - cal_ux(i)));
}
}
vector<int>lab(n);
auto find_set = [&] (int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
};
unordered_map<int, bool>vis;
function<bool(int)>is_balance = [&] (int d0x){
int c0 = 0, cu = 0;
vector<int>ver;
for(int i = 0; i < n; i++){
if(cal_0x(i) == d0x){
ver.push_back(i);
}
else if(cal_0x(i) < d0x){
c0++;
}
else{
cu++;
}
}
if(max(c0, cu) > (n >> 1)){
return false;
}
if(ver.size() <= (n >> 1)){
return true;
}
int candidate, cnt = 0;
iota(lab.begin(), lab.end(), 0);
for(int i = c0 + cu, cnt_2 = 0; i < ver.size(); i++){
if(cnt == 0){
candidate = ver[i];
cnt++;
cnt_2 = 0;
}
else if(cal_ix(candidate) + cal_ix(ver[i]) == ask(candidate, ver[i])){
cnt--;
}
else{
lab[ver[i]] = candidate;
cnt++;
if(++cnt_2 > (n >> 1)){
return false;
}
}
}
if(cnt == 0){
return true;
}
candidate = find_set(candidate);
for(int i = cnt = 0; i < n; i++){
if(find_set(i) == candidate){
cnt++;
}
}
for(int i = 0; i < ver.size() && cnt <= (n >> 1); i++){
if(find_set(ver[i]) != candidate && cal_ix(find_set(ver[i])) + cal_ix(candidate) != ask(candidate, find_set(ver[i]))){
lab[find_set(ver[i])] = candidate;
for(int j = cnt = 0; j < n; j++){
if(find_set(j) == candidate){
cnt++;
}
}
}
}
return cnt <= (n >> 1);
};
for(int i = 0, rod_0 = rod_0 = (ask(0, u) + ask(0, v) - diam) >> 1; i < n; i++){
if(cal_0x(i) >= rod_0 && min_rad == max(cal_ux(i), diam - cal_ux(i))){
int d0x = cal_0x(i);
if(!vis[d0x]){
vis[d0x] = true;
if(is_balance(d0x)){
return min_rad;
}
}
}
}
return -min_rad;
}
}
int hubDistance(int _n, int subtask_id){
memset(cache, -1, sizeof(cache));
n = _n;
for(int i = 0; i < n; i++){
cache[i][i] = 0;
}
if(subtask_id == 1){
return sub1::solve();
}
if(subtask_id == 2){
return sub2::solve();
}
return sub345::solve();
}
