#include "rail.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=5005;
int kesh[maxn][maxn],N,idxC,idxD,poz[maxn],tip[maxn],D,A,B;
vector<pair<int,int>> V;
queue<int> Q;
int dist(int a,int b){
if(a==b)
return 0;
if(kesh[a][b]==-2){
// cout<<a<<" - "<<b<<": ";
int x=getDistance(a,b);
// cout<<x<<endl;
kesh[a][b]=kesh[b][a]=x;
}
return kesh[a][b];
}
int distc(int x){
return dist(A,x)-dist(A,B)+D;
}
set<int> PC,PD;
bool lint(int l,int r,int x){ /// Unutra je D
// cout<<"LEFT INTERVAL "<<l<<" "<<r<<" "<<x<<endl;
int p=poz[l]+dist(l,x);
if(p>=poz[r])
return false;
auto it=PC.upper_bound(p);
it--;
int d=*it;
if(poz[r]-d+p-d==dist(r,x))
return true;
return false;
}
bool rint(int l,int r,int x){ /// Unutra je C
//cout<<"RIGHT INTERVAL "<<l<<" "<<r<<" "<<x<<endl;
int p=poz[r]-dist(r,x);
if(p<=poz[l])
return false;
// cout<<p<<endl;
auto it=PD.upper_bound(p);
int d=*it;
//cout<<d<<endl;
if(d-poz[l]+d-p==dist(l,x))
return true;
return false;
}
void findLocation(int n, int first, int location[], int stype[]){
N=n;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
kesh[i][j]=-2;
location[0]=first;
stype[0]=1;
if(N==1)
return;
if(N==2){
stype[1]=2;
location[1]=first+dist(0,1);
return;
}
for(int i=1;i<N;i++)
V.push_back({dist(0,i),i});
sort(V.begin(),V.end());
idxC=0;
poz[0]=first;
tip[0]=1;
idxD=V[0].s;
poz[idxD]=first+dist(0,idxD);
tip[idxD]=2;
for(int i=1;i<V.size();i++)
Q.push(V[i].second);
A=idxC;
B=idxD;
PC.insert(poz[A]);
PD.insert(poz[B]);
int xx=Q.front();
Q.pop();
if(dist(B,xx)+dist(A,B)==dist(A,xx)){
tip[xx]=1;
poz[xx]=poz[B]-dist(B,xx);
PC.insert(poz[xx]);
D=dist(B,xx);
}
else{
tip[xx]=2;
poz[xx]=poz[A]+dist(A,xx);
PD.insert(poz[xx]);
D=(dist(B,xx)-(dist(A,xx)-dist(A,B)))/2;
}
while(Q.size()){
int x=Q.front();
Q.pop();
if(rint(A,B,x)){
//cout<<x<<" A"<<endl;
tip[x]=1;
poz[x]=poz[B]-dist(x,B);
PC.insert(poz[x]);
continue;
}
if(distc(x)>dist(x,B)){
if(lint(idxC,B,x)){
// cout<<x<<" B"<<endl;
tip[x]=2;
poz[x]=poz[idxC]+dist(idxC,x);
PD.insert(poz[x]);
}
else{
// cout<<x<<" C"<<endl;
tip[x]=1;
poz[x]=poz[B]-dist(B,x);
PC.insert(poz[x]);
idxC=x;
}
}
else{
if(rint(A,idxD,x)){
// cout<<x<<" D"<<endl;
tip[x]=1;
poz[x]=poz[idxD]-dist(idxD,x);
PC.insert(poz[x]);
}
else{
// cout<<x<<" E"<<endl;
tip[x]=2;
poz[x]=poz[A]+dist(A,x);
PD.insert(poz[x]);
idxD=x;
}
}
}
for(int i=1;i<N;i++){
location[i]=poz[i];
stype[i]=tip[i];
}
}
/*
3
15
1 8
1 1
1 2
1 3
2 4
2 5
1 6
2 7
2 9
2 10
1 11
1 12
2 13
1 14
2 15
1
4
1 1
2 4
2 7
2 9
2
6
1 3
2 6
2 7
1 1
1 0
2 8
3
8
1 1
1 3
2 10
1 12
2 18
2 19
1 25
2 26
*/
