#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int dist[5002][5002];
int span[5002];
bool U[5002];
void findLocation(int N, int first, int location[], int stype[])
{
for(int i=0;i<N;i++)
{
for(int j=i+1;j<N;j++)
{
dist[i][j] = getDistance(i, j);
dist[j][i] = dist[i][j];
}
}
U[0] = 1;
stype[0] = 1;
location[0] = first;
for(int i=1;i<N;i++) span[i] = 0;
for(int i=1;i<N;i++)
{
int opt = -1;
for(int j=0;j<N;j++)
{
if(U[j]) continue;
if(opt == -1 || dist[span[opt]][opt] > dist[span[j]][j]) opt = j;
}
int pr = span[opt];
U[opt] = true;
stype[opt] = 3 - stype[pr];
if(stype[pr] == 1) location[opt] = location[pr] + dist[opt][pr];
else location[opt] = location[pr] - dist[opt][pr];
for(int j=0;j<N;j++) if(dist[span[j]][j] > dist[opt][j]) span[j] = opt;
}
}
