#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int f[110][110];
// int getDistance(int x , int y){
// return f[x][y];
// }
int sub1(int N,int sub){
int n = N;
pair <int,int> tmp;
vector <int> val , value;
val.assign(n,0);
value.assign(n,0);
for (int i = 1 ; i < n ; i++){
int x = getDistance(0,i);
tmp = max(tmp,make_pair(x,i));
}
int u = tmp.second;
tmp.first = 0;
for (int i = 0 ; i < n ; i++)
if (i != u){
int x = getDistance(i,u);
val[i] = x;
tmp = max(tmp,make_pair(x,i));
}
int v = tmp.second;
int R = 1e9;
//cout << u << " " << v << "\n";
for (int i = 0 ; i < n ; i++)
if (i != u && i != v){
int x = getDistance(v,i);
value[i] = x;
int y = val[i];
int z = val[v];
int a = (x + y - z)/2;
int b = x - a;
int c = z - b;
int r = max(a,max(b,c));
if (r < R){
tmp = make_pair(b,c);
R = r;
}
}
if (sub < 3) return R;
// cout << tmp.first << " " << tmp.second << "\n";
int cntu = 1 , cntv = 1 , cnt = 0;
for (int i = 0 ; i < n ; i++)
if (i != u && i != v)
{
int x = val[i];
int y = val[v];
int z = value[i];
int a = (x + y - z)/2;
// cout << i << " " << a << '\n';
if (a < tmp.second) cntu++;
if (a == tmp.second) cnt++;
if (a > tmp.second) cntv++;
}
// cout << cntu << " " << cntv << " " << cnt << "\n";
if (cntu > n/2 || cntv > n/2 || cnt > n/2) return -R;
return R;
}
vector <pair<int,int> > adj[510];
vector <pair<int,int> > dis[510] ,pos[1000010];
int cnt = 0;
int tk[510] = {0};
int dfs(int u , int par){
int res = 0;
for (pair <int,int> v : adj[u])
if (v.first != par){
// cout << v.first << " " << v.second << "\n";
int x = dfs(v.first,u);
res = max(res,x + v.second);
}
return res;
}
int DFS(int u, int par, int t,int n){
int d = (u < n);
tk[u] = 1;
for (pair<int,int> v : adj[u])
if (v.first != par && v.first != t){
d += DFS(v.first,u,t,n);
}
return d;
}
int sub3(int n){
for (int i = 0 ; i <= 500 ; i++){
adj[i].clear();
dis[i].clear();
}
vector <vector<int> > val;
vector <int> value;
int m = n;
val.assign(n,vector<int>(n,0));
for (int i = 0 ; i < n ; i++)
for (int j = i + 1; j < n ; j++) {
int x = getDistance(i,j);
val[i][j] = x;
val[j][i] = x;
}
pair<int,int> tmp(1e9,1e9);
for (int i = 1 ; i < n ; i++)
for (int j = i + 1 ; j < n ; j++){
int x = val[i][j];
int y = val[0][i];
int z = val[0][j];
int a = (x + y - z)/2;
int b = x - a;
int c = z - b;
int ok = 0;
for (pair<int,int> v : pos[c]){ //cout << v.first << " " << v.second << "\n";
if (val[v.first][0] - c + val[i][0] - c == val[v.first][i] ||
val[v.first][0] - c + val[j][0] - c == val[v.first][j]){
ok = v.second;
break;
}
}
// cout << i << " " << j << " " << a << " " << b << " " << c << " " << ok << "\n";
if (!ok)
{
ok = m++;
pos[c].push_back(make_pair(i,ok));
value.push_back(c);
}
dis[i].push_back(make_pair(a,ok));
dis[j].push_back(make_pair(b,ok));
tmp = min(tmp,make_pair(c,ok));
}
dis[0].push_back(tmp);
for (int i = 0 ; i < n ; i++){
sort(dis[i].begin(),dis[i].end());
dis[i].resize(unique(dis[i].begin(),dis[i].end()) - dis[i].begin());
if (!dis[i].empty()){
adj[i].push_back(make_pair(dis[i][0].second,dis[i][0].first));
adj[dis[i][0].second].push_back(make_pair(i,dis[i][0].first));
}
for (int j = 1 ; j < dis[i].size() ; j++){
adj[dis[i][j].second].push_back(make_pair(dis[i][j - 1].second,dis[i][j].first - dis[i][j - 1].first));
adj[dis[i][j - 1].second].push_back(make_pair(dis[i][j].second,dis[i][j].first - dis[i][j - 1].first));
}
}
for (int i = 0 ; i < m; i++){
sort(adj[i].begin(),adj[i].end());
adj[i].resize(unique(adj[i].begin(),adj[i].end()) - adj[i].begin());
// for (pair<int,int> v : adj[i]) cout << i << " " << v.first << "\n";
}
int R = 1e9 , ok = 0;
for (int i = n ; i < m ; i++){
int x = dfs(i,i);
// cout << x << " " << i << "\n";
if (x < R){
ok = 1;
R = x;
memset(tk,0,sizeof(tk));
for (int j = 0 ; j < m ; j++)
if (i != j && !tk[j]){
int d = DFS(j,j,i,n);
if (d > n/2) ok = 0;
// if (i == 13) cout << j << " " << d << "\n";
}
}
}
for (int v : value) pos[v].clear();
if (!ok) R = -R;
return R;
}
int hubDistance(int N, int sub) {
if (sub < 3 || sub == 4) return sub1(N,sub);
return sub3(N);
}
// int main(){
// freopen("txt.inp","r",stdin);
// freopen("txt.out","w",stdout);
// int n;
// cin >> n;
// for (int i = 0 ; i < n ; i++)
// for (int j = 0 ; j < n ; j++)
// cin >> f[i][j];
// cout << hubDistance(n,3);
// return 0;
// }
