#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int dp[5000][5000];
int get(int a,int b){
if(a == b)
return 0;
if(dp[a][b] || dp[b][a])
return max(dp[a][b],dp[b][a]);
return dp[a][b] = getDistance(a,b);
}
void findLocation(int n, int first, int location[], int stype[]){
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
dp[i][j] = 0;
}
}
location[0] = first;
stype[0] = 1;
if(n == 1)return;
vector<int> ord0;
for(int i = 0;i<n;i++){
if(i != 0){
ord0.push_back(i);
}
}
sort(ord0.begin(),ord0.end(),[&](int a,int b){
return get(0,a) < get(0,b);
});
int posD = ord0[0];
location[posD] = location[0] + get(0,posD);
stype[posD] = 2;
for(int i = 1;i<ord0.size();i++){
if(stype[ord0[i]])continue;
if(get(0,ord0[i]) == get(posD,ord0[i]) + get(0,posD)){
stype[ord0[i]] = 1;
location[ord0[i]] = location[posD] - get(posD,ord0[i]);
for(int j = 0;j<n;j++){
if(stype[j])continue;
if(get(0,j) == get(posD,j) + get(0,posD)){
if(get(posD,j) ==get(posD,ord0[i]) + get(ord0[i],j)){
stype[j] = 2;
location[j] = location[ord0[i]] + get(ord0[i],j);
}
}
}
}
}
vector<int> ordD;
for(int i = 0;i<n;i++){
if(i != posD){
ordD.push_back(i);
}
}
sort(ordD.begin(),ordD.end(),[&](int a,int b){
return get(posD,a) < get(posD,b);
});
for(int i = 1;i<ordD.size();i++){
if(stype[ordD[i]])continue;
if(get(posD,ordD[i]) == get(0,ordD[i]) + get(posD,0)){
stype[ordD[i]] = 2;
location[ordD[i]] = location[0] + get(0,ordD[i]);
for(int j = 0;j<n;j++){
if(stype[j])continue;
if(get(posD,j) == get(0,j) + get(posD,0)){
if(get(0,j) == get(0,ordD[i]) + get(ordD[i],j)){
stype[j] = 1;
location[j] = location[ordD[i]] - get(ordD[i],j);
}
}
}
}
}
}
