#include "rail.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN=5005,INF=1e9;
int d[MAXN][MAXN];
void findLocation(int N, int first, int location[], int stype[])
{
stype[0]=1;location[0]=first;
fore(i,0,N)fore(j,i+1,N){
d[i][j]=d[j][i]=getDistance(i,j);
}
vector<int>dist(N,INF);
vector<bool>vis(N,0);
using T=tuple<int,int,int>;
priority_queue<T,vector<T>,greater<T>>pq;
dist[0]=0;
vis[0]=1;
fore(i,1,N){
if(dist[i]>d[0][i]){
dist[i]=d[0][i];
pq.push({d[0][i],0,i});
}
}
while(SZ(pq)){
auto[sum,from,to]=pq.top();pq.pop();
if(vis[to])continue;
vis[to]=1;
stype[to]=(stype[from]==1?2:1);
location[to]=location[from]+(stype[from]==1?d[from][to]:-d[from][to]); // como determino el bloque?
fore(i,1,N){
if(vis[i])continue;
if(dist[i]>d[to][i]){
dist[i]=d[to][i];
pq.push({dist[i],to,i});
}
}
}
//~ fore(i,0,N)cout<<stype[i]<<" ";
//~ cout<<endl;
//~ fore(i,0,N)cout<<location[i]<<" ";
return;
}
// ( ) )
