#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> dist;
void dfs(int cur, int pai, int N, int marc[], int location[], int stype[]);
void findLocation(int N, int first, int location[], int stype[])
{
int marc[N];
dist[make_pair(0, 0)] = 1e6;
location[0] = first, stype[0] = 1;
for(int i = 0; i < N; i++) marc[i] = 0;
dfs(0, 0, N, marc, location, stype);
return;
}
void dfs(int cur, int pai, int N, int marc[], int location[], int stype[]){
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(stype[cur] == 1) location[viz] = location[cur] + dist[make_pair(cur, viz)], stype[viz] = 2;
else location[viz] = location[cur] - dist[make_pair(cur, viz)], stype[viz] = 1;
dfs(viz, cur, N, marc, location, stype);
}
}
