#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define debug(x) cerr << #x << ": " << x << endl;
#define sep ' '
#define X first
#define Y second
const ll MAXN = 5000 + 10;
int n, f, D[MAXN][MAXN], best[MAXN], best_par[MAXN];
bool vis[MAXN];
inline int get(int i, int j) {
return getDistance(i, j);
}
void findLocation(int N, int first, int location[], int stype[]) {
n = N;
f = first;
location[0] = f;
stype[0] = 1;
if (n == 1) return;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x = get(i, j);
D[i][j] = D[j][i] = x;
}
}
for (int i = 1; i < n; i++)
best[i] = D[0][i], best_par[i] = 0;
vis[0] = true;
for (int i = 1; i < n; i++) {
int v = -1;
for (int u = 1; u < n; u++) {
if (vis[u]) continue;
if (v == -1 || best[u] < best[v])
v = u;
}
int p = best_par[v];
vis[v] = true;
stype[v] = 3 - stype[p];
location[v] = (stype[v] == 2 ? 1 : -1) * best[v] + location[p];
for (int u = 0; u < n; u++) {
if (!vis[u] && D[v][u] < best[u]) {
best[u] = D[v][u];
best_par[u] = v;
}
}
}
/*
for (int i = 0; i < n; i++)
cerr << stype[i] << sep << location[i] << endl;
*/}
// mn location
