#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using Node = array<int, 3>;
int dist[5005][5005];
void findLocation(int N, int first, int location[], int stype[]) {
stype[0] = 1; location[0] = first;
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++) dist[i][j] = dist[j][i] = getDistance(i, j);
priority_queue<Node, vector<Node>, greater<Node> > pq;
vector<bool> vis(N); vis[0] = 1;
vector<int> D(N, 1e9); D[0] = 0;
for(int i=1; i<N; i++) pq.push({ D[i] = dist[0][i], i, 0 });
while(!pq.empty()) {
auto [d, a, b] = pq.top(); pq.pop();
if(vis[a]) continue;
vis[a] = 1;
stype[a] = 3 - stype[b];
location[a] = location[b] + (stype[b] == 1 ? dist[a][b] : -dist[a][b]);
for(int c=0; c<N; c++) {
if(vis[c]) continue;
if(D[c] > dist[a][c]) pq.push({ D[c] = dist[a][c], c, a });
}
}
}
