#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
const int N = 5000;
int dist[N][N];
vector<int> adj[N];
void Dfs(int u, int type, int location[], int stype[]){
assert(stype[u] != 3 - type);
if (stype[u])
return;
stype[u] = type;
for(int v : adj[u]){
location[v] = location[u] + (type == 1? dist[u][v] : -dist[u][v]);
Dfs(v, 3 - type, location, stype);
}
}
void findLocation(int n, int first, int location[], int stype[]){
for(int i = 0; i < n; i++){
dist[i][i] = 1e9;
for(int j = i + 1; j < n; j++)
dist[i][j] = dist[j][i] = getDistance(i, j);
}
for(int u = 0; u < n; u++){
int v = 0;
for(int i = 0; i < n; i++)
if (dist[u][v] > dist[u][i])
v = i;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 0; i < n; i++)
stype[i] = 0;
location[0] = first;
Dfs(0, 1, location, stype);
int a = 0, b = 0;
for(int i = 0; i < n; i++)
if (stype[i] && location[i] > location[b])
b = i;
for(int i = 0; i < n; i++)
if (!stype[i] && min(dist[i][a], dist[i][b]) < dist[a][b]){
if (dist[i][b] < dist[i][a]){
location[i] = location[b] - dist[i][b];
stype[i] = 1;
} else {
location[i] = location[a] + dist[i][a];
stype[i] = 2;
}
}
while (true){
int u = b;
for(int i = 0; i < n; i++)
if (!stype[i] && dist[i][b] < dist[i][a] && dist[u][b] > dist[i][b])
u = i;
if (u != b){
location[u] = location[b] - dist[u][b];
Dfs(u, 1, location, stype);
} else {
break;
}
}
while (true){
int u = a;
for(int i = 0; i < n; i++)
if (!stype[i] && dist[i][a] < dist[i][b] && dist[u][a] > dist[i][a])
u = i;
if (u != a){
location[u] = location[a] + dist[u][a];
Dfs(u, 2, location, stype);
} else {
break;
}
}
}
