#include "rail.h"
#include <bits/stdc++.h>
#define printPii(p) printf("%d %d\n" , p.ff , p.ss )
#define lp(i,a,b) for(int i = a ;i<b;i++)
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define sz size()
#define mk make_pair
const int MAXN = 5e3+10 ;
const int inf = 1e9+10 ;
using namespace std ;
int n ;
int ini[2] , idx[2] ;
int m[MAXN][MAXN] ;
bool marc[MAXN] ;
vector<int> jaFoi[2] ;
vector<pii> dist[2] ;
void findDistance(int source, int whereToSave, bool yes)
{
marc[source] = true ;
lp(i,0,n)
if(!marc[i])
{
m[source][i] = getDistance(source, i) ;
if(yes)
dist[whereToSave].pb( { m[source][i] , i } ) ;
}
if(yes)
sort( dist[whereToSave].begin() , dist[whereToSave].end() ) ;
}
void findLocation(int N, int first, int location[], int stype[])
{
n = N ;
location[0] = first , stype[0] = 1 ;
if(n==1) return ;
findDistance(0,0,1);
ini[1] = dist[0][0].ss ;
findDistance(ini[1],1,1);
dist[0].resize(0) ;
ini[0] = dist[1][0].ss ;
findDistance(ini[0],0,1);
location[ini[1]] = first + m[0][ini[1]] ;
location[ini[0]] = location[ini[1]] - m[ini[1]][ini[0]] ;
stype[ini[1]] = 2 ;
stype[ini[0]] = 1 ;
lp(i,0,2) dist[i].pb({inf,inf}) ;
jaFoi[1].pb(ini[0]) ;
jaFoi[0].pb(ini[1]) ;
m[ini[0]][ini[1]] = m[ini[1]][ini[0]] ;
while(true)
{
pii p0 = dist[0][ idx[0] ] , p1 = dist[1][ idx[1] ] ;
if(p0.ff == inf && p1.ff == inf) { break ; }
int cur = p0.ss , cameFrom = 0 ;
if(p0.ff > p1.ff)
cur = p1.ss, cameFrom = 1 ;
idx[cameFrom] ++ ;
if( marc[cur] ) { continue ; }
int fatMult = cameFrom == 0 ? 1 : -1 ;
int contFatMult = fatMult == -1 ? 1 : -1 ;
for(int i : jaFoi[cameFrom])
if( m[ini[cameFrom]][i] + m[i][cur] == m[ini[cameFrom]][cur] )
{
location[cur] = location[i] + m[i][cur] * contFatMult ;
stype[cur] = stype[i] ;
marc[cur] = true ;
break ;
}
if(marc[cur]) continue ;
location[cur] = location[ini[cameFrom]] + m[ini[cameFrom]][cur] * fatMult ;
stype[cur] = stype[ini[!cameFrom]] ;
jaFoi[cameFrom].pb(cur) ;
findDistance(cur,0,0) ;
}
}
