#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;
for(int i = 0 ; i < n ; i++) for(int j = i + 1 ; j < n ; j++)
{
int x = getDistance(i , j);
dis[i][j] = dis[j][i] = x;
}
vector <int> vec;
for(int i = 1 ; i < n ; i++)
vec.push_back(i);
sort(vec.begin() , vec.end() , cmpR);
for(int i = 0 ; i < n - 1 ; i++)
{
int las = 0;
for(int j = 0 ; j < i ; j++) if(dis[0][vec[j]] + dis[vec[j]][vec[i]] == dis[0][vec[i]])
las = vec[j];
Update(las , vec[i]);
}
for(int i = 0 ; i < n ; i++)
{
location[i] = loc[i];
stype[i] = ty[i];
//cout << i << " " << ty[i] << " " << loc[i] << endl;
}
}
/*
3
11
1 4
1 5
2 6
1 7
2 8
1 9
2 3
1 2
2 1
2 10
1 0
*/
