#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int M = 5005, inf = 1e9;
int d[M][M], p;
int getd (int I, int J) {
if(I == J) return 0;
if(I > J) swap(I, J);
if(!d[I][J]) d[I][J] = getDistance(I, J);
return d[I][J];
}
bool cmp (int A, int B) {
return getd(p, A) < getd(p, B);
}
void solve (int L[], int S[], vector<int> &X, int P, int Q) {
p = P;
sort(X.begin(), X.end(), cmp);
for(auto &T : X) {
if(getd(Q, T) + getd(P, Q) == getd(P, T)) {
L[T] = L[Q] + (1 - 2*(S[P] == 1)) * getd(Q, T);
S[T] = S[P];
}
else {
L[T] = L[P] - (1 - 2*(S[P] == 1)) * getd(P, T);
S[T] = S[Q];
Q = T;
}
}
}
void findLocation(int N, int F, int L[], int S[])
{
L[0] = F;
S[0] = 1;
if(N == 1) return;
int I = 0, V = inf;
for(int i=1; i<N; i++){
int T = getd(0, i);
if(V > T) {
I = i;
V = T;
}
}
L[I] = L[0] + getd(0, I);
S[I] = 2;
vector<int> X, Y;
for(int i=1; i<N; i++) {
if(i == I) continue;
if(getd(I, i) + getd(I, 0) == getd(0, i)) {
if(getd(I, 0) > getd(I, i)) {
L[i] = getd(I, 0) - getd(I, i);
S[i] = 1;
}
else X.push_back(i);
}
else Y.push_back(i);
}
solve(L, S, X, I, 0);
solve(L, S, Y, 0, I);
}
