#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5010;
int n;
map<pair<int, int>, int> dist;
int marc[MAXN], loc[MAXN], tp[MAXN];
void dfs(int cur, int pai);
void findLocation(int N, int first, int location[], int stype[])
{
dist[make_pair(0, 0)] = 1e6;
n = N;
loc[0] = first, tp[0] = 1;
dfs(0, 0);
for(int i = 0; i < N; i++) location[i] = loc[i], stype[i] = tp[i];
return;
}
void dfs(int cur, int pai){
marc[cur] = 1;
set<pair<int, int> > aux;
for(int i = 0; i < n; i++){
if(marc[i]) continue;
if(dist[make_pair(cur, i)] == 0) dist[make_pair(cur, i)] = dist[make_pair(i, cur)] = getDistance(cur, i);
aux.insert(make_pair(dist[make_pair(cur, i)], i));
}
while(!aux.empty()){
int viz = aux.begin()->second;
aux.erase(aux.begin());
if(marc[viz]) continue;
if(dist[make_pair(cur, viz)] > dist[make_pair(pai, viz)]) continue;
if(tp[cur] == 1) loc[viz] = loc[cur] + dist[make_pair(cur, viz)], tp[viz] = 2;
else loc[viz] = loc[cur] - dist[make_pair(cur, viz)], tp[viz] = 1;
dfs(viz, cur);
}
}
