#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);
}
