#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/ioi14_d1/debug.h"
#else
#define debug(...) void(37)
#endif
template<typename T>
vector<T> inverse_fuck(T* a, int N) {
vector<T> res(N);
for (int i = 0; i < N; ++i) {
res[i] = a[i];
}
return res;
}
const int MAX = int(2e6);
void findLocation(int N, int first, int location[], int stype[]) {
location[0] = first, stype[0] = 1;
if (N == 1) {
return;
}
vector<vector<int>> mem(N, vector<int>(N));
auto Dist = [&](int i, int j) {
if (i > j) {
swap(i, j);
}
return mem[i][j] = (mem[i][j] != 0 || i == j ? mem[i][j] : getDistance(i, j));
};
int match = 1;
for (int i = 2; i < N; ++i) {
debug(Dist(0, i));
if (Dist(0, i) < Dist(0, match)) {
match = i;
}
}
debug(match);
vector<int> between, left, right;
for (int i = 1; i < N; ++i) {
if (i == match) {
continue;
}
debug(Dist(match, i), Dist(0, i));
if (Dist(match, i) + Dist(0, match) == Dist(0, i)) {
if (Dist(0, i) < 2 * Dist(0, match)) {
between.push_back(i);
} else {
left.push_back(i);
}
} else {
right.push_back(i);
}
}
auto Solve = [&](int root, vector<int> s, int fill) {
sort(s.begin(), s.end(), [&](int x, int y) {
return Dist(root, x) < Dist(root, y);
});
vector<int> placed = {fill};
int last = root ^ match ^ 0;
vector<tuple<int, int, int>> res;
int breaks = -1;
vector<bool> used(MAX + 1);
for (auto x : s) {
int pos = -1, type = 0;
int g = Dist(x, last);
int inside = Dist(root, last) - g;
debug(g, inside, Dist(root, last));
int next = int(lower_bound(placed.begin(), placed.end(), inside) - placed.begin());
if (inside > fill && placed[next] != inside && 2 * placed[next] - inside == Dist(root, x)) {
pos = inside;
type = 0;
} else {
pos = Dist(root, x);
type = 1;
last = x;
placed.push_back(pos);
}
used[pos] = true;
res.emplace_back(x, pos, type);
}
return res;
};
int fill = Dist(0, match);
auto l = Solve(match, left, fill), r = Solve(0, right, fill);
debug(left, l);
debug(right, r);
debug(between);
for (auto[x, p, t] : r) {
location[x] = p + location[0];
stype[x] = t + 1;
}
for (auto x : between) {
location[x] = location[0] + 2 * Dist(0, match) - Dist(0, x);
stype[x] = 1;
}
for (auto[x, p, t] : l) {
location[x] = location[0] + Dist(0, match) - p;
stype[x] = (t ^ 1) + 1;
}
stype[match] = 2;
location[match] = location[0] + Dist(0, match);
for (int x = 0; x < N; ++x) {
debug(x, location[x], stype[x]);
}
return;
}
