#include "rail.h"
//#include "grader.cpp"
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
using namespace std;
const int MAXN = 5005;
int askedAlready[MAXN][MAXN];
int ask(int x, int y)
{
if(x>y) swap(x, y);
if(askedAlready[x][y]==-1) askedAlready[x][y] = getDistance(x, y);
return askedAlready[x][y];
}
int dist[MAXN], origin[MAXN];
bool done[MAXN];
void findLocation(int N, int first, int location[], int stype[])
{
memset(askedAlready, -1, sizeof(askedAlready));
memset(done, false, sizeof(done));
done[0] = true;
stype[0] = 0;
location[0] = first;
int lastDone = 0;
for(int i = 0;i<N;i++)
{
dist[i] = 1e9;
}
for(int iter = 0;iter<N-1;iter++)
{
//cout << " ---- " << lastDone << " ---- " << '\n';
for(int x = 0;x<N;x++)
{
if(done[x]==true) continue;
//cout << dist[x] << " != " << getDistance(x, lastDone) << '\n';
//assert(ask(x, lastDone)!=dist[x]);
if(ask(x, lastDone)<dist[x])
{
dist[x] = ask(x, lastDone);
origin[x] = lastDone;
//if(x==1) cout << " -> " << origin[x] << " || " << lastDone << '\n';
}
}
int newDone = -1;
for(int x = 0;x<N;x++)
{
if(done[x]==true) continue;
if(newDone==-1 || dist[x]<dist[newDone]) newDone = x;
}
stype[newDone] = stype[ origin[newDone] ]^1;
//cout << newDone << " from " << origin[newDone] << '\n';
if(stype[ origin[newDone] ]==0)
location[newDone] = location[ origin[newDone] ] + dist[newDone];
else
location[newDone] = location[ origin[newDone] ] - dist[newDone];
done[newDone] = true;
lastDone = newDone;
}
for(int i = 0;i<N;i++) stype[i]++;
//for(int i = 0;i<N;i++)
// cout << i << " -> " << location[i] << " " << stype[i] << '\n';
}
/*
1
6
1 2
1 3
1 1
2 4
2 5
2 6
*/
