#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 m[MAXN][MAXN] , loc[MAXN] , type[MAXN] ;
void run(int sc , vector<int> conj , int mult )
{
if(conj.sz ==0) return ;
vector<pii> aux ;
for(int i : conj) aux.pb( {m[sc][i] , i} ) ;
sort(aux.begin() , aux.end()) ;
int frontier = aux[0].ss ;
loc[frontier] = loc[sc] + m[sc][frontier] * mult ;
type[frontier] = type[sc] == 1 ? 2 : 1 ;
lp(i,1,aux.sz)
{
bool ok = true ;
int now = aux[i].ss ;
m[frontier][now] = getDistance(frontier, now) ;
lp(j,0,i)
{
int t = aux[j].ss ;
if( type[t] == type[sc] ) continue ;
if( m[sc][t] * 2 + m[frontier][now] - m[sc][frontier] == m[sc][now] )
{
ok = false ;
loc[now] = loc[frontier] - m[frontier][now] * mult;
type[now] = type[sc] ;
}
}
if(!ok) continue ;
loc[now] = loc[sc] + m[sc][now] * mult ;
type[now] = type[sc] == 1 ? 2 : 1 ;
frontier = now ;
}
}
void findLocation(int n, int first, int location[], int stype[])
{
loc[0] = first ;
type[0] = 1 ;
if( n == 1 ) return ;
vector<pii> aux ;
lp(i,1,n)
{
m[0][i] = m[i][0] = getDistance(0,i) ;
aux.pb({m[0][i] , i}) ;
}
sort(aux.begin() , aux.end() ) ;
int other = aux[0].ss ;
loc[other] = loc[0] + m[0][other] ;
type[other] = 2 ;
lp(i,1,n)
if(i != other)
m[i][other] = m[other][i] = getDistance(i,other) ;
vector<int> v[3] ;
lp(i,1,n)
{
if( i == other ) continue ;
int d1 = m[0][i] , d2 = m[other][i] , d = m[0][other] ;
if( d1 == d2 + d && d2 > d ) v[0].pb(i) ;
else if( d1 == d2 + d && d2 <= d) v[1].pb(i) ;
else v[2].pb(i) ;
}
for(int i : v[1])
{
loc[i] = loc[other] - m[other][i] ;
type[i] = 1 ;
}
run( 0 , v[2] , 1 ) ;
run(other, v[0] , -1 ) ;
lp(i,0,n) location[i] = loc[i] ;
lp(i,0,n) stype[i] = type[i] ;
}
