#include <bits/stdc++.h>
using namespace std;
#include "rail.h"
#define all(x) x.begin(), x.end()
int n;
vector<bool> found;
vector<vector<int>> d;
int getDistance(int i, int j);
void findLocation(int n, int first, int location[], int stype[])
{
::n = n;
location[0] = first;
stype[0] = 1;
d = vector<vector<int>>(n, vector<int>(n, 1e9));
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
d[i][j] = d[j][i] = getDistance(i, j);
int b = min_element(all(d[0])) - d[0].begin();
location[b] = first + d[0][b];
stype[b] = 2;
int a = min_element(all(d[b])) - d[b].begin();
location[a] = location[b] - d[b][a];
stype[a] = 1;
set<int> left, right;
for (int i = 0; i < n; i++)
{
if (i == a || i == b)
continue;
if (d[a][i] < d[b][i])
right.insert(i);
else
left.insert(i);
}
auto solveSide = [&](set<int> group, int flip, int a, int b)
{
while (group.size())
{
int c = -1;
int dist = 1e9;
for (int x : group)
if (d[a][x] < dist)
dist = d[a][x], c = x;
location[c] = location[a] + (flip ? -dist : dist);
stype[c] = 2 - flip;
int D = -1;
for (int x : group)
if (d[c][x] < dist)
dist = d[c][x], D = x;
if (D != -1)
{
location[D] = location[c] - (flip ? -dist : dist);
stype[D] = 1 + flip;
vector<int> toRemove;
for (int x : group)
if (d[c][x] < d[D][x])
{
location[x] = location[c] - (flip ? -d[c][x] : d[c][x]);
stype[x] = 1 + flip;
toRemove.push_back(x);
}
for (int x : toRemove)
group.erase(x);
a = D;
b = c;
}
group.erase(c);
group.erase(D);
}
};
solveSide(right, 0, a, b);
solveSide(left, 1, b, a);
}
