#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
struct UnionFind {
int par[N], sz[N];
void init() {
iota(par, par+N, 0);
fill_n(sz, N, 1);
}
int find(int x) {
return par[x] = x == par[x] ? x : find(par[x]);
}
void unite(int a, int b) {
a = find(a), b = find(b);
if(a == b) return;
par[a] = b, sz[b] += sz[a];
}
int size(int a) {
return sz[find(a)];
}
} dsu;
int hubDistance(int n, int sub) {
vector<vector<int> > d(N, vector<int>(N, 0));
auto get_dist = [&](int a, int b) {
if(a == b) return 0;
else if(d[a][b]) return d[a][b];
else return d[a][b] = d[b][a] = getDistance(a, b);
};
int a, b;
for(int i = 0, mx = -1; i < n; i++) if(get_dist(0, i) > mx) a = i, mx = get_dist(0, i);
for(int i = 0, mx = -1; i < n; i++) if(get_dist(a, i) > mx) b = i, mx = get_dist(a, i);
int lim = (get_dist(a, b) + get_dist(a, 0) - get_dist(b, 0)) / 2;
vector<int> hub;
int root1 = -1, root2 = -1, ans = INT_MAX;
for(int i = 0; i < n; i++) {
int pos = (get_dist(a, i) + get_dist(a, 0) - get_dist(i, 0)) / 2;
int now = max(pos, get_dist(a, b) - pos);
hub.emplace_back(pos);
if(now <= ans) {
if(now < ans) root1 = pos, root2 = -1;
else {
if(root1 == -1) root1 = pos;
else if(pos != root1) root2 = pos;
}
ans = now;
}
}
sort(hub.begin(), hub.end());
hub.resize(unique(hub.begin(), hub.end()) - hub.begin());
// printf("root = %d %d\n", root1, root2);
// for(int i : hub) printf("%d ", i);
// printf("\n");
auto chk = [&](int root) {
int l = 0, r = 0;
for(int i = 0; i < n; i++) {
int pos = (get_dist(a, i) + get_dist(a, 0) - get_dist(i, 0)) / 2;
if(pos < root) ++l;
if(pos > root) ++r;
}
return (l <= n / 2 && r <= n / 2);
};
if(!chk(root1)) root1 = -1;
if(root2 == -1 || !chk(root2)) root2 = -1;
if(root1 == -1 && root2 == -1) return -ans;
if(root1 < root2) swap(root1, root2);
auto same = [&](int x, int y) {
if(x == y) return true;
int d = get_dist(a, x) + get_dist(0, y) - get_dist(a, 0);
return d != get_dist(x, y);
};
auto chk2 = [&](int root) {
dsu.init();
vector<int> v;
for(int i = 0; i < n; i++) {
int pos = (get_dist(a, i) + get_dist(a, 0) - get_dist(i, 0)) / 2;
if(pos == root) v.emplace_back(i);
}
for(int i = 0; i < v.size(); i++) for(int j = 0; j < v.size(); j++) {
if(same(v[i], v[j])) dsu.unite(v[i], v[j]);
}
for(int i = 0; i < v.size(); i++) if(dsu.size(v[i]) > n / 2) return false;
return true;
};
if(!chk2(root1) && (root2 == -1 || !chk2(root2))) return -ans;
else return ans;
auto vote = [&](int root) {
vector<int> v, type;
for(int i = 0; i < n; i++) {
int pos = (get_dist(a, i) + get_dist(a, 0) - get_dist(i, 0)) / 2;
if(pos == root) v.emplace_back(i);
}
int last = -1, cnt = 0;
for(int i = 0; i < v.size(); i++) {
if(last == -1) {
last = v[i], ++cnt;
type.emplace_back(0);
} else if(same(v[i], last)) {
++cnt;
type.emplace_back(1);
} else {
--cnt;
if(cnt == 0) last = -1;
type.emplace_back(2);
}
}
if(last == -1) return true;
int sz = 0;
for(int i = 0; i < v.size(); i++) sz += same(v[i], last);
return sz <= n / 2;
};
if(!vote(root1) && (root2 == -1 || !vote(root2))) return -ans;
else return ans;
}
