/**
* user: ppavic
* fname: Patrik
* lname: Pavić
* task: towns
* score: 0.0
* date: 2019-06-23 11:08:12.761811
*/
#include "towns.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define PB push_back
#define X first
#define Y second
using namespace std;
const int N = 505;
const int INF = 0x3f3f3f3f;
typedef pair < int, int > pii;
typedef vector < pii > vp;
typedef vector < int > vi;
int dis[N][N], un[N], sk, n;
vp v[N];
void spajaj(){
int piv = 0, edg = 0;
for(;!un[piv];piv++);
vi klik;
for(int i = 0;i < n;i++){
if(i == piv || !un[i]) continue;
int mx = -INF, mi = INF;
for(int j = 0;j < n;j++){
if(j == i) continue;
if(j == piv || !un[j]) continue;
mi = min(mi, dis[i][j] - dis[piv][j]);
mx = max(mi, dis[i][j] - dis[piv][j]);
}
//printf("mi %d mx %d i %d piv %d\n", mi, mx, i, piv);
if(mi != mx) continue;
if(dis[piv][n] && dis[piv][n] != (dis[i][piv] - mi) / 2) continue;
dis[piv][n] = (dis[i][piv] - mi) / 2;
dis[i][n] = (dis[i][piv] + mi) / 2;
dis[n][i] = dis[i][n];
dis[n][piv] = dis[piv][n];
v[n].PB({i, dis[i][n]});
v[i].PB({n, dis[i][n]});
//printf("%d spojena na %d s tezinom %d\n", i, n, dis[i][n]);
sk--;// un[i] = 0;
klik.PB(i);
}
for(int x : klik) un[x] = 0;
v[n].PB({piv, dis[piv][n]});
v[piv].PB({n, dis[piv][n]});
//printf("%d spojena na %d s tezinom %d\n", piv, n, dis[piv][n]);
un[n] = 1; un[piv] = 0;
for(int i = 0;i < n;i++){
if(!un[i]) continue;
dis[n][i] = dis[piv][i] - dis[piv][n];
//printf("dis %d %d je %d\n", n, i, dis[n][i]);
dis[i][n] = dis[n][i];
}
n++;
//printf("gotov\n");
}
int R(int x,int lst){
int ret = 0;
for(pii y : v[x]){
if(y.X == lst) continue;
ret = max(R(y.X, x) + y.Y, ret);
}
return ret;
}
int C(int x,int lst){
if(v[x].size() == 1) return 1;
int ret = 0;
for(pii y : v[x]){
if(y.X == lst) continue;
ret += C(y.X, x);
}
return ret;
}
int hubDistance(int nn, int sub) {
for(int i = 0;i < N;i++) v[i].clear(), un[i] = 0;
memset(dis, 0, sizeof(dis));
n = nn;
for(int i = 0;i < n;i++){
dis[i][i] = 0; un[i] = 1;
for(int j = i + 1;j < n;j++){
dis[i][j] = getDistance(i, j);
dis[j][i] = dis[i][j];
}
}
sk = n;
int T = 0;
while(sk > 1){
spajaj();
}
int ans = INF, ima = 0;
for(int i = nn;i < n;i++)
ans = min(ans, R(i, i));
for(int i = nn;i < n;i++){
if(R(i, i) != ans) continue;
int pos = 1;
for(pii y : v[i]){
if(C(y.X, i) > 2 * n) pos = 0;
}
ima += pos;
}
if(sub < 3) return ans;
if(ima) return ans;
return -ans;
}
