#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int N, minx = 10000000, minid, A[100009], T[100009], dp[5009][5009];
vector<pair<int, int>> vec1, vec2;
int getDist(int u, int v) {
if (u == v) return 0;
if (u > v) swap(u, v);
if (dp[u][v] >= 1) return dp[u][v];
int E = getDistance(u, v);
dp[u][v] = E;
return E;
}
void solve_1() {
int pos = 0; vector<int> E; E.push_back(0);
for (int i = 0; i < vec1.size(); i++) {
if (vec1[i].first < minx) {
T[vec1[i].second] = 1;
A[vec1[i].second] = A[minid] - vec1[i].first;
}
else {
int Z1 = getDist(minid, vec1[i].second);
int Z2 = getDist(minid, pos);
int Z3 = getDist(pos, vec1[i].second);
int Z = A[pos] + Z3;
for (int j = 0; j < E.size(); j++) {
if (abs(A[minid] - A[E[j]]) + abs(A[E[j]] - Z) == Z1) {
A[vec1[i].second] = Z;
T[vec1[i].second] = 2;
break;
}
}
if (T[vec1[i].second] == 0) {
A[vec1[i].second] = A[minid] - Z1;
T[vec1[i].second] = 1;
pos = vec1[i].second;
E.push_back(vec1[i].second);
}
}
}
}
void solve_2() {
int pos = minid; vector<int> E; E.push_back(minid);
for (int i = 0; i < vec2.size(); i++) {
int Z1 = getDist(0, vec2[i].second);
int Z2 = getDist(0, pos);
int Z3 = getDist(pos, vec2[i].second);
int Z = A[pos] - Z3;
for (int j = 0; j < E.size(); j++) {
if (abs(A[0] - A[E[j]]) + abs(A[E[j]] - Z) == Z1) {
A[vec2[i].second] = Z;
T[vec2[i].second] = 1;
break;
}
}
if (T[vec2[i].second] == 0) {
A[vec2[i].second] = A[0] + Z1;
T[vec2[i].second] = 2;
pos = vec2[i].second;
E.push_back(vec2[i].second);
}
}
}
void findLocation(int n, int first, int location[], int stype[]) {
N = n; A[0] = first; T[0] = 1;
for (int i = 1; i < N; i++) {
int E = getDist(0, i);
if (minx > E) { minx = E; minid = i; }
}
A[minid] = A[0] + minx; T[minid] = 2;
int minv = 10000000; for (int i = 0; i < N; i++) { if (i == minid) continue; minv = min(minv, getDist(minid, i)); }
for (int i = 0; i < N; i++) {
if (i == 0 || i == minid) continue;
int V1 = getDist(0, i) - (minx - minv);
int V2 = getDist(minid, i);
if (V1 > V2) vec1.push_back(make_pair(V2, i));
else vec2.push_back(make_pair(V1 + (minx - minv), i));
}
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
//cout << endl;
//cout << "Base value:" << endl;
//cout << minx << " " << minid << endl;
//cout << endl;
//cout << "Value of vec1:" << endl;
//for (int i = 0; i < vec1.size(); i++) cout << "(" << vec1[i].first << ", " << vec1[i].second << ")" << endl;
//cout << endl;
//cout << "Value of vec2:" << endl;
//for (int i = 0; i < vec2.size(); i++) cout << "(" << vec2[i].first << ", " << vec2[i].second << ")" << endl;
//cout << endl;
solve_1();
solve_2();
for (int i = 0; i < N; i++) {
//cout << "(" << A[i] << ", " << T[i] << ")" << endl;
location[i] = A[i]; stype[i] = T[i];
}
}
