#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 5003;
int n;
int ans[N][N];
int qry(int x, int y)
{
if (ans[x][y] != -1)
return ans[x][y];
return ans[x][y] = ans[y][x] = getDistance(x, y);
}
int getnext(int s, int location[], int stype[])
{
int minu = N * 5;
int minx;
for (int x = 0; x < n; ++x)
{
if (x == s)
continue;
if (qry(s, x) < minu)
{
minu = qry(s, x);
minx = x;
}
}
if (stype[s] == 1)
{
stype[minx] = 2;
location[minx] = location[s] + qry(s, minx);
}
else
{
stype[minx] = 1;
location[minx] = location[s] - qry(s, minx);
}
return minx;
}
bool c[N];
int go(int x, int location[], int stype[])
{
int u = getnext(x, location, stype);
int s = getnext(u, location, stype);
memset(c, false, sizeof c);
c[u] = true;
while (1)
{
int minu = N * 5;
int minx;
for (int x = 0; x < n; ++x)
{
if (x == s)
continue;
if (c[x])
continue;
if (qry(s, x) < qry(u, x))
{
if (qry(s, x) < minu)
{
minu = qry(s, x);
minx = x;
}
}
}
if (minu == N * 5)
break;
if (stype[s] == 1)
{
stype[minx] = 2;
location[minx] = location[s] + qry(s, minx);
}
else
{
stype[minx] = 1;
location[minx] = location[s] - qry(s, minx);
}
u = minx;
c[u] = true;
}
return u;
}
void findLocation(int N_, int first, int location[], int stype[])
{
n = N_;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i == j)
continue;
ans[i][j] = -1;
}
}
location[0] = first;
stype[0] = 1;
int x = go(0, location, stype);
x = go(x, location, stype);
x = go(x, location, stype);
x = go(x, location, stype);
x = go(x, location, stype);
}
