#include "rail.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5005;
int kesh[maxn][maxn],N,idxC,idxD,poz[maxn],tip[maxn];
int dist(int a,int b){
if(a==b)
return 0;
if(kesh[a][b]==0){
// cout<<a<<" - "<<b<<": ";
int x=getDistance(a,b);
// cout<<x<<endl;
kesh[a][b]=kesh[b][a]=x;
}
return kesh[a][b];
}
void findLocation(int n, int first, int location[], int stype[]){
N=n;
location[0]=first;
stype[0]=1;
int najb=1;
for(int i=1;i<N;i++)
if(dist(0,i)<dist(0,najb))
najb=i;
tip[najb]=2;
poz[najb]=first+dist(0,najb);
idxD=najb;
// cout<<"IDX D "<<idxD<<endl;
idxC=0;
for(int i=0;i<N;i++)
if(dist(idxD,i)<dist(idxD,idxC) and i!=idxD)
idxC=i;
//cout<<"IDX C "<<idxC<<endl;
tip[idxC]=1;
poz[idxC]=poz[idxD]-dist(idxD,idxC);
for(int i=1;i<N;i++){
if(i==idxC or i==idxD)
continue;
int dc=dist(i,idxC);
int dd=dist(i,idxD);
if(dd<dc){
tip[i]=1;
poz[i]=poz[idxD]-dd;
}
else{
tip[i]=2;
poz[i]=poz[idxC]+dc;
}
}
for(int i=1;i<N;i++){
location[i]=poz[i];
stype[i]=tip[i];
}
}
