#include "rail.h"
#include <vector>
#include <algorithm>
using namespace std;
#define X first
#define Y second
#define PB push_back
const int N = 5055;
const int M = 1e6 + 500;
typedef pair < int, int > pii;
int dis[N][N], par[N], m, ty[N], l[N];
vector < pii > v[M];
vector < int > g[N];
void dfs(int x,int lst){
//printf("X = %d TY = %d L = %d\n", x, ty[x], l[x]);
for(int y : g[x]){
if(y == lst) continue;
ty[y] = !ty[x];
if(ty[x]) l[y] = l[x] - dis[x][y];
else l[y] = l[x] + dis[x][y];
dfs(y, x);
}
}
void findLocation(int n, int first, int loc[], int type[]){
l[0] = first;
for(int i = 0;i < n;i++){
par[i] = i;
for(int j = i + 1;j < n;j++){
dis[i][j] = getDistance(i, j);
dis[j][i] = dis[i][j];
if(dis[i][j] >= M) continue;
v[dis[i][j]].PB({i, j});
}
}
for(int i = 0;i < M;i++){
for(pii vv : v[i]){
if(par[vv.X] == par[vv.Y]) continue;
//printf("evo me %d %d\n", v[i].X, v[i].Y);
int r = par[vv.Y];
for(int i = 0;i < n;i++){
if(par[i] == r)
par[i] = par[vv.X];
}
g[vv.X].PB(vv.Y);
g[vv.Y].PB(vv.X);
}
}
dfs(0,0);
for(int i = 0;i < n;i++){
type[i] = ty[i] + 1;
loc[i] = l[i];
}
}
