#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];
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;
}
}
priority_queue<pair<pll, int>, vector<pair<pll, int>>, greater<pair<pll, int>>> pq;
for (int i = 1; i < n; i++) pq.push({{D[0][i], i}, 0});
vis[0] = true;
for (int i = 1; i < n; i++) {
while (vis[pq.top().X.Y]) pq.pop();
auto [e, p] = pq.top();
auto [d, v] = e;
stype[v] = (3 - stype[p]);
location[v] = (stype[v] == 2 ? 1 : -1) * D[p][v] + location[p];
vis[v] = true;
for (int i = 0; i < n; i++)
pq.push({{D[v][i], i}, v});
}
/*
for (int i = 0; i < n; i++)
cerr << stype[i] << sep << location[i] << endl;
*/}
// mn location
