#include "rail.h"
#include <map>
using namespace std;
map<int, int> cache[1000'000];
int GetDistance(int u, int v)
{
auto it = cache[u].find(v);
if (it != cache[u].end()) return it->second;
return cache[u][v] = getDistance(u, v);
}
void findLocation(int n, int first, int location[], int stype[])
{
int mn = 1;
for (int i = 1; i < n; ++i)
{
if (GetDistance(0, i) < GetDistance(0, mn))
mn = i;
}
location[0] = first;
stype[0] = 1;
location[mn] = first + GetDistance(0, mn);
stype[mn] = 2;
for (int i = 1; i < n; ++i)
{
if (i == mn) continue;
if (GetDistance(0, mn) + GetDistance(mn, i) == GetDistance(0, i))
{
stype[i] = 1;
location[i] = location[mn] - GetDistance(mn, i);
}
else
{
stype[i] = 2;
location[i] = first + GetDistance(0, i);
}
}
}
