#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 5e3 + 20;
int d[maxn][maxn];
void findLocation(int N, int first, int location[], int stype[])
{
int n = N;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
d[i][j] = d[j][i] = getDistance(i , j);
vector<pair<int , int> > tmp;
for(int i = 1; i < n; i++)
tmp.pb({d[0][i] , i});
sort(tmp.begin() , tmp.end());
vector<int> rd;
for(auto x : tmp)
{
int v = x.second;
bool bad = 0;
if(!rd.empty())
{
int lx = d[0][rd.back()] - d[rd.back()][v];
int tmp = -1;
for(auto u : rd)
if(d[0][u] >= lx)
{
tmp = u;
break;
}
if(d[0][v] == d[v][tmp] + d[tmp][0])
bad = 1;
}
if(!bad)
rd.pb(v) , stype[v] = 2;
}
tmp.clear();
while(rd.empty());
int r = rd.back();
for(int i = 0; i < n; i++)
if(i != r)
tmp.pb({d[r][i] , i});
sort(tmp.begin() , tmp.end());
vector<int> c;
for(auto x : tmp)
{
int v = x.second;
bool bad = 0;
for(auto u : c)
if(d[r][v] == d[r][u] + d[u][v])
bad = 1;
if(!bad)
c.pb(v) , stype[v] = 1;
}
for(int i = 0; i < n; i++)
if(!stype[i])
stype[i] = 2;
location[r] = first + d[0][r];
for(int i = 0; i < n; i++)
if(stype[i] == 1)
location[i] = location[r] - d[r][i];
for(int i = 0; i < n; i++)
if(stype[i] == 2)
location[i] = location[c.back()] + d[c.back()][i];
}
