#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
void findLocation(int n, int first, int location[], int stype[]) {
for (int i=0; i<n; i++) {
location[i] = -1;
}
location[0] = first;
if (n==1) {
return;
}
stype[0] = 1;
int c;
vector<int> dis(n);
dis[0] = 0;
for (int i=1; i<n; i++) {
dis[i] = getDistance(0, i);
}
int mn=1e9;
for (int i=1; i<n; i++) {
if (dis[i] < mn) {
c = i;
mn = dis[i];
}
}
vector<int> disc(n);
disc[c] = 0;
for (int i=0; i<n; i++) {
disc[i] = getDistance(i, c);
}
stype[c] = 2;
location[c] = location[0] + dis[c];
for (int i=0; i<n; i++) {
if (i==0 || i==c) continue;
if (dis[i] != dis[c]+disc[i] || disc[i] > location[c]) continue;
if (dis[i] == dis[c]+disc[i]) {
stype[i] = 1;
location[i] = location[c]-disc[i];
}
else {
continue;
}
}
int left=0;
mn = location[0];
for (int i=0; i<n; i++) {
//cout << i << " " << location[i] << endl;
if (location[i] >= 0 && location[i] < mn && stype[i]==1) {
mn = location[i];
left = i;
}
}
for (int i=0; i<n; i++) {
if (location[i] <= -1) {
int dist = getDistance(left, i);
//cout << location[left] << " " << dist << endl;
location[i] = location[left] + dist;
stype[i] = 2;
}
}
}
