#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
int i, j, f, s, r = 99999999;
vector<vector<int> > v(N);
vector<int> di(N, r), cl(N);
for (i = 1; i < N; i++)
location[i] = stype[i] = -1;
for (i = 0; i < N; i++)
{
v[i].resize(N);
for (j = 0; j < N; j++)
{
if (j < i)
v[i][j] = v[j][i];
else if (j == i)
v[i][j] = 0;
else
v[i][j] = getDistance(i, j);
if (v[i][j] && v[i][j] < di[i])
{
di[i] = v[i][j];
cl[i] = j;
}
}
}
f = cl[0];
location[f] = first + di[0];
stype[f] = 2;
s = cl[f];
location[s] = location[f] - di[f];
stype[s] = 1;
for (i = 1; i < N; i++)
{
if (i == f || i == s)
continue;
if (v[i][f] < v[i][s])
{
if (cl[i] == f || v[cl[i]][f] > v[i][f])
{
location[i] = location[f] - v[i][f];
stype[i] = 1;
}
else
{
location[i] = location[f] - 2 * v[cl[i]][f] + v[i][f];
stype[i] = 2;
}
}
else
{
if (cl[i] == s || v[cl[i]][s] > v[i][s])
{
location[i] = location[s] + v[i][s];
stype[i] = 2;
}
else
{
location[i] = location[s] + 2 * v[cl[i]][s] - v[i][s];
stype[i] = 1;
}
}
}
}
