#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int AN = 1007;
int vis[AN];
int dis[2][AN];
int centd;
void Clean(int n)
{
centd = 0;
for(int r = 0; r < 2; ++r)
for(int i = 0; i < n + 3; ++i)
dis[r][i] = 0;
for(int i = 0; i < n; ++i)
vis[i] = 0;
}
void Do(int n, int &a, int &b)
{
pair<int, int> ma = make_pair(-1, -1);
for(int i = 1; i < n; ++i)
{
dis[0][i] = getDistance(0, i);
ma = max(ma, make_pair(dis[0][i], -i));
}
a = -ma.nd;
dis[1][0] = ma.st;
ma = make_pair(dis[1][0], 0);
for(int i = 1; i < n; ++i)
{
if(i == a) continue;
dis[1][i] = getDistance(a, i);
ma = max(ma, make_pair(dis[1][i], -i));
}
b = -ma.nd;
}
void Fix(vector<int> &a)
{
vector<int> nw;
sort(a.begin(), a.end());
for(int i = 0; i < (int)a.size(); ++i)
if(i == 0 || a[i] != a[i - 1])
nw.pb(a[i]);
a = nw;
}
int D(int x)
{
return (dis[1][0] + dis[1][x] - dis[0][x]) / 2;
}
int Dc(int x)
{
int ans = dis[1][x] - D(x);
int dod = D(x) - centd;
if(dod < 0) dod *= -1;
return ans + dod;
}
bool Cp(int a, int b)
{
return (getDistance(a, b) != Dc(a) + Dc(b));
}
bool Check(int n)
{
//cerr << "\n\n";
int cur = 0;
vector<int> v;
for(int i = 0; i < n; ++i)
{
if(v.size() == 0)
{
v.pb(i);
++cur; vis[i] = cur;
continue;
}
if(Cp(v[0], i))
{
v.pb(i);
vis[i] = cur;
}else
{
v.pop_back();
}
}
//for(int i = 0; i < n; ++i)
//cerr << "V: " << i << " " << vis[i] << " " << Dc(i) << "\n";
if(v.size() == 0) return true;
int il = 0, u = v[0];
for(int i = 0; i < n; ++i)
{
if(vis[i] == -1) continue;
if(vis[i] == vis[u])
{++il; continue;}
if(vis[i] == 0)
{
if(Cp(u, i)) ++il;
continue;
}
bool czy = Cp(u, i);
if(czy) ++il;
for(int j = i + 1; j < n; ++j)
if(vis[j] == vis[i])
{
vis[j] = -1;
if(czy) ++il;
}
}
if(il <= (n / 2)) return true;
return false;
}
int hubDistance(int _NN, int _sub)
{
//cerr << "\n";
Clean(_NN);
int n = _sub;
n = _NN;
int a, b;
Do(n, a, b);
vector<int> pth;
int xd = D(b);
for(int i = 0; i < n; ++i)
{
int cur = D(i);
if(cur <= xd)
pth.pb(cur);
//cerr << i << " " << D(i) << "\n";
}
//cerr << a << " " << b << " xd " << xd << "\n";
Fix(pth);
int ans = II; int pos = -1;
for(int i = 0; i < (int)pth.size(); ++i)
{
if(max(pth[i], dis[1][b] - pth[i]) < ans)
pos = i;
ans = min(ans, max(pth[i], dis[1][b] - pth[i]));
}
int il = 0;
for(int i = 0; i < n; ++i)
if(D(i) <= pth[pos])
++il;
if(il <= (n / 2) && pos < (int)pth.size() - 1 && ans == max(pth[pos + 1], dis[1][b] - pth[pos + 1])) ++pos;
centd = pth[pos];
//cerr << centd << "\n";
bool m = Check(n);
if(!m) ans *= -1;
return ans;
}
