#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using pp=pair<int,int>;
#define all(v) (v).begin(), (v).end()
#define pb push_back
int dcache[5000][5000];
int get_dist(int a, int b){
if(dcache[a][b]) return dcache[a][b]-1;
int d = getDistance(a, b);
dcache[a][b] = d+1;
return d;
}
vector<pp> ds;
vector<int> lv, rv;
void findLocation(int n, int first, int location[], int stype[])
{
if(n == 1){
location[0] = first;
stype[0] = 1;
return;
}
static bool first_run = true;
if(!first_run) memset(dcache, -1, sizeof(dcache)), ds.clear(), lv.clear(), rv.clear();
first_run = false;
for(int i=1; i<n; ++i) ds.emplace_back(get_dist(0, i), i);
sort(all(ds));
int diam, ri;
tie(diam, ri) = ds[0];
int rp = first + diam;
location[0] = first; stype[0] = 1;
location[ri] = rp; stype[ri] = 2;
for(int i=1; i<n; ++i) if(i != ri){
int dl = get_dist(0, i);
int dr = get_dist(ri, i);
if(dr < diam && dl == diam + dr){
location[i] = rp - dr;
stype[i] = 1;
continue;
}
if(dl == dr + diam) lv.pb(i);
else rv.pb(i);
}
int lp = first, li = 0;
for(int i : lv){
int ld = get_dist(li, i);
if(get_dist(ri, i) == (rp-lp) + ld){
location[i] = lp + ld;
stype[i] = 2;
} else {
lp = location[i] = rp - get_dist(ri, i);
stype[i] = 1;
li = i;
}
}
for(int i : rv){
int rd = get_dist(ri, i);
if(get_dist(0, i) == (rp-first) + rd){
location[i] = rp - rd;
stype[i] = 1;
} else {
rp = location[i] = first + get_dist(0, i);
stype[i] = 2;
ri = i;
}
}
}
