#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
#define Fi first
#define Se second
using pii = pair<int, int>;
const int MAXN = 5e3;
const int MAXM = 1e6;
int d[MAXN][MAXN];
bool isD[MAXM], isC[MAXM];
int getDistance(int i, int j);
int Dist(int i, int j) {
if(i > j) swap(i, j);
if(d[i][j] == 0) {
d[i][j] = getDistance(i, j);
}
return d[i][j];
}
void findLocation(int n, int first, int location[], int stype[]) {
location[0] = first;
stype[0] = 1;
int MinDist = 1e9, X;
for(int station = 1; station < n; station++) {
if(Dist(0, station) < MinDist) {
MinDist = Dist(0, station);
X = station;
}
}
location[X] = location[0] + MinDist;
stype[X] = 2;
vector<pii> vcc1, vcc2;
for(int station = 1; station < n; station++) {
if(station == X) continue;
bool cond_1 = (Dist(0, station) == Dist(0, X) + Dist(X, station));
bool cond_2 = (Dist(0, X) < Dist(X, station));
if(cond_1 && cond_2) {
vcc2.push_back({Dist(X, station), station});
}
else {
vcc1.push_back({Dist(0, station), station});
}
}
sort(vcc1.begin(), vcc1.end());
sort(vcc2.begin(), vcc2.end());
isD[location[X]] = true;
int Y = X;
for(int i = 0; i < vcc1.size(); i++) {
int station = vcc1[i].Se;
int z = Dist(0, Y) + Dist(Y, station) - Dist(0, station);
if(isD[location[Y] - z/2]) {
location[station] = location[Y] - Dist(Y, station);
stype[station] = 1;
}
else {
location[station] = location[0] + Dist(0, station);
stype[station] = 2;
isD[location[station]] = true;
Y = station;
}
}
isC[location[0]] = true;
Y = 0;
for(int i = 0; i < vcc2.size(); i++) {
int station = vcc2[i].Se;
int z = Dist(X, Y) + Dist(Y, station) - Dist(X, station);
if(isC[location[Y] + z/2]) {
location[station] = location[Y] + Dist(Y, station);
stype[station] = 2;
}
else {
location[station] = location[X] - Dist(X, station);
stype[station] = 1;
isC[location[station]] = true;
Y = station;
}
}
}
