#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 5e3 + 20;
int d[maxn][maxn];
int get(int i , int j)
{
if(i != j && !d[i][j])
d[i][j] = d[j][i] = getDistance(i , j);
return d[i][j];
}
void findLocation(int N, int first, int location[], int stype[])
{
int n = N;
vector<pair<int , int> > tmp;
for(int i = 1; i < n; i++)
tmp.pb({get(0 , i) , i});
sort(tmp.begin() , tmp.end());
vector<int> rd , shit;
for(auto x : tmp)
{
int v = x.second;
bool bad = 0;
if(!rd.empty())
{
int lx = get(0 , rd.back()) - get(rd.back() , v);
int tmp = -1;
for(auto u : rd)
if(get(0 , u) >= lx)
{
tmp = u;
break;
}
if(get(0 , v) == get(v , tmp) + get(tmp , 0))
bad = 1;
}
if(!bad)
location[v] = get(0 , v) , rd.pb(v) , stype[v] = 2;
else
{
if(get(0 , rd.back()) - get(rd.back() , v) > 0)
stype[v] = 1 , location[v] = get(0 , rd.back()) - get(rd.back() , v);
else
{
d[rd[0]][v] = d[v][rd[0]] = d[0][v] - d[0][rd[0]];
shit.pb(v);
}
}
}
int r = rd[0];
rd.clear() , tmp.clear();
rd.pb(0);
for(auto v : shit)
{
bool bad = 0;
if(!rd.empty())
{
int lx = get(r , rd.back()) - get(rd.back() , v);
int tmp = -1;
for(auto u : rd)
if(get(r , u) >= lx)
{
tmp = u;
break;
}
if(get(r , v) == get(v , tmp) + get(tmp , r))
bad = 1;
}
if(!bad)
location[v] = location[r] - get(r , v) , rd.pb(v) , stype[v] = 1;
else
{
if(get(r , rd.back()) - get(rd.back() , v) > 0)
stype[v] = 2 , location[v] = location[r] - (get(r , rd.back()) - get(rd.back() , v));
else
{
cout << "HERE" << endl;
assert(0);
}
}
}
for(int i = 0; i < n; i++)
location[i] += first;
stype[0] = 1;
}
