#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
#define pb push_back
#define fi first
#define se second
const int INF = (int)(1e9);
typedef pair<int,int> ii;
int dist[5005][5005];
int d(int a,int b){
if(dist[a][b]!=-1)return dist[a][b];
return dist[a][b]=dist[b][a]=getDistance(a,b);
}
int flip(int x){
if(x==1)return 2;
return 1;
}
int pivot;
bool compare(ii a,ii b){
if(d(a.se,pivot)<d(b.se,pivot))return 1;
else if(d(a.se,pivot)>d(b.se,pivot))return 0;
return a.se<b.se;
}
void findLocation(int N, int first, int location[], int stype[])
{
memset(dist,-1,sizeof dist);
for (int i = 0; i < N; ++i)
stype[i]=0;
location[0]=first;
stype[0]=1;
if(N==1)return;
int x=-1,D=INF;
for (int i = 1; i < N; ++i)
{
if(d(0,i)<D)
x=i,D=d(0,i);
}
//cerr<<x<<"\n";
location[x]=first+D,stype[x]=2;
vector<ii> R,L,M;
for (int y = 1; y < N; ++y)
{
if(y==x)continue;
if((d(x,y)+d(0,x)) == d(0,y))L.pb({d(x,y),y});
//else if(d(x,y)<d(x,0))M.pb({d(x,y),y});
else R.pb({d(0,y),y});
}
sort(R.begin(),R.end());
sort(L.begin(),L.end());
sort(M.begin(),M.end());
if(sz(R)){
//int a=x;
/*stype[a]=2;
location[a]=location[0]+R[0].fi;*/
vector<int> h={x};
for (int i = 0; i < sz(R); ++i)
{
//cerr<<d(0,R[i].se)-d(0,a)-d(R[i].se,a)<<"\n";
//pivot=R[i].se;
//sort(R.begin()+i,R.end(),compare);
for(auto a:h){
//cerr<<a<<"\n";
if(d(0,R[i].se)==(d(R[i].se,a)+d(0,a))){
location[R[i].se]=location[a]-d(R[i].se,a),stype[R[i].se]=1;
}
}
if(!stype[R[i].se])location[R[i].se]=location[0]+d(0,R[i].se),stype[R[i].se]=2,h.pb(R[i].se);
}
}
if(sz(L)){
//int a=0;
/*for(auto it:L)
cerr<<it.se<<" ";
cerr<<"L ended ***********\n";*/
/*stype[a]=1;
location[a]=location[x]-L[0].fi;*/
vector<int> h={0};
for (int i = 0; i < sz(L); ++i)
{
//pivot=L[i].se;
//sort(L.begin()+i,L.end(),compare);
for(auto a:h)
if(d(x,L[i].se)==(d(L[i].se,a)+d(x,a)))location[L[i].se]=location[a]+d(L[i].se,a),stype[L[i].se]=2;
if(!stype[L[i].se])location[L[i].se]=location[x]-d(x,L[i].se),stype[L[i].se]=1,h.pb(L[i].se);
//cout<<stype[L[i].se]<<" "<<location[L[i].se]<<"\n";
}
}
//cerr<<"-------\n";
// cerr<<sz(M)<<"\n";
/*for(auto it:M){
//cerr<<location[it.se]
stype[it.se]=1;
location[it.se]=location[x]-it.fi;
}*/
/*for (int i = 0; i < N; ++i)
{
//assert(stype[i]!=-1);
//cout<<stype[i]<<" "<<location[i]<<"\n";
}*/
//cerr<<"\n";//
}
