#include "towns.h"
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <map>
constexpr int maxn = 300;
int dp[maxn][maxn], c[maxn];
std::map<int, std::vector<int>> filhos;
int get(int i, int j) {
if(i > j) std::swap(i, j);
return dp[i][j] != -1 ? dp[i][j] : dp[i][j] = getDistance(i, j);
}
struct DSU
{
int pai[maxn], peso[maxn];
void init() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
int find(int x) { return pai[x] == x?x:pai[x]=find(pai[x]); }
void join(int a, int b) {
a = find(a), b = find(b);
if(a == b) return;
if(peso[a] < peso[b])
std::swap(a, b);
pai[b] = a;
peso[a] += peso[b];
}
int sz(int x) { return peso[find(x)]; }
} dsu;
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
int hubDistance(int N, int sub) {
memset(dp, -1, sizeof dp);
memset(c, 0, sizeof c);
filhos.clear();
int a = 0, b = 0, dist = 0;
for(int i = 0; i < 2; i++) {
for(int j = 0; j < N; j++) {
if(a != j) {
int v = get(a, j);
if(v > dist) b = j, dist = v;
}
}
if(!i) a = b, dist = 0, b = 0;
}
int R = 0x3f3f3f3f;
for(int i = 0; i < N; i++) {
if(i == a || i == b) continue;
int d1 = get(a, i), d2 = get(b, i);
c[i] = (d1 + d2 - dist) >> 1;
R = min(R, max(d1, d2) - c[i]);
filhos[d1-c[i]].push_back(i);
}
// if(sub <= 2) return R;
// int sz = 1;
// bool ok = 0;
// for(auto it : filhos) {
// if(it.first == R || it.first == dist - R) {
// // if(sz <= (N >> 1) && N - sz - it.second <= (N >> 1)
// // && it.second <= (N >> 1)) ok = 1;
// if(sz > (N >> 1) && N - sz - it.second > (N >> 1)) continue;
// }
// sz += it.second;
// }
// return R * (ok?1:-1);
if(sub <= 2) return R;
if(sub != 3) assert(0);
// printf("A %d, B %d\n", a, b);
int sz = 1;
bool ok = 0;
for(auto it : filhos) {
// printf("%d %d %ld\n", it.first, sz, it.second.size());
// for(int x : it.second)
// printf("%d\n", x);
// printf("\n");
if(it.first != R && it.first != dist - R) {
sz += (int)(it.second).size();
continue;
}
if(sz <= (N >> 1) && N - sz - (int)(it.second).size() <= (N >> 1)) ok = 1;
std::vector<int> v = (it.second);
int n = (int)v.size();
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
if(get(v[i], v[j]) != c[v[i]] + c[v[j]])
dsu.join(v[i], v[j]);
for(int i = 0; i < n; i++)
if(dsu.sz(v[i]) > (N >> 1)) ok = 0;
sz += n;
}
// printf("ok %d\n", ok);
return R * (ok?1:-1);
}
