#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
const int N = 5e3 + 10;
int dis[N][N] , n , f , s , loc[N] , ty[N];
vector <int> L , R;
bool cmpR(int a , int b)
{
return dis[0][a] < dis[0][b];
}
bool cmpL(int a , int b)
{
return dis[s][a] < dis[s][b];
}
void Update(int from , int to)
{
//cout << from << " -> " << to << endl;
ty[to] = 3 - ty[from];
if(ty[from] == 1)
loc[to] = loc[from] + dis[from][to];
else
loc[to] = loc[from] - dis[from][to];
}
void SolveR()
{
if(R.empty())
return;
sort(R.begin() , R.end() , cmpR);
int las = R[0];
Update(0 , las);
for(int i = 1 ; i < R.size() ; i++)
{
int now = R[i];
dis[las][now] = getDistance(las , now);
if(dis[las][now] < dis[0][las])
Update(las , now);
else
{
Update(0 , now);
las = now;
}
}
}
void SolveL()
{
if(L.empty())
return;
sort(L.begin() , L.end() , cmpL);
int las = 0;
for(int i = 0 ; i < L.size() ; i++)
{
int now = L[i];
if(dis[s][now] < dis[s][0])
{
Update(s , now);
continue;
}
dis[las][now] = getDistance(las , now);
if(dis[las][now] < dis[s][las])
Update(las , now);
else
{
Update(s , now);
las = now;
}
}
}
void findLocation(int nn , int first, int location[], int stype[])
{
n = nn;
loc[0] = first;
ty[0] = 1;
s = -1;
for(int i = 1 ; i < n ; i++)
{
dis[0][i] = getDistance(0 , i);
//cout << i << " WTF " << dis[0][i] << endl;
if(s == -1 || dis[0][i] < dis[0][s])
s = i;
}
//cout << "S : " << s << endl;
Update(0 , s);
dis[s][0] = dis[0][s];
for(int i = 1 ; i < n ; i++) if(i != s)
{
dis[s][i] = getDistance(s , i);
//cout << i << " : " << dis[0][i] << " " << dis[s][i] << endl;
if(dis[s][i] < dis[0][i])
L.push_back(i);
else
{
//cout << "WER WER WER WER " << endl;
R.push_back(i);
}
}
SolveR();
SolveL();
for(int i = 0 ; i < n ; i++)
{
location[i] = loc[i];
stype[i] = ty[i];
//cout << i << " : " << loc[i] << " " << ty[i] << endl;
}
}
/*
4
11
1 4
1 5
2 6
1 7
2 8
1 9
2 3
1 2
2 1
2 10
1 0
*/
