#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << ": " << x << endl;
#define sep ' '
#define X first
#define Y second
const ll MAXN = 5000 + 10;
const ll INF = 1e9 + 10;
int n, f, D[MAXN][MAXN], pos[MAXN], TTop[MAXN], Q;
bool vis[MAXN];
inline int get(int i, int j) {
if (i > j) swap(i, j);
if (i == j) return 0;
if (!D[i][j]) {
assert(Q < 3 * (n - 1));
D[i][j] = getDistance(i, j); // fuck
Q++;
}
return D[i][j];
}
inline void solve(int s, vector<int> vec) {
if (vec.empty()) return;
map<int, int> mp;
sort(all(vec), [s] (int i, int j) {
return get(s, i) < get(s, j);
});
int lst = vec.front();
vec.erase(vec.begin());
pos[s] = 0;
pos[lst] = get(s, lst);
TTop[lst] = 1;
mp[pos[lst]] = lst;
mp[pos[s]] = s; // fuck
for (int e : vec) {
int poss = pos[lst] - get(lst, e);
bool flag = true;
if (poss <= pos[s]) flag = false;
int t = get(s, e) - poss;
if (!flag || t < 0 || t % 2) flag = false;
else {
t /= 2;
int tpos = poss + t;
if (mp.find(tpos) == mp.end()) flag = false;
else flag = TTop[mp[tpos]];
}
flag ^= 1;
TTop[e] = flag;
if (TTop[e] == 0) pos[e] = pos[lst] - get(e, lst);
else {
lst = e;
pos[e] = pos[s] + get(s, e);
}
mp[pos[e]] = e;
}
}
void findLocation(int N, int first, int location[], int stype[]) {
n = N;
f = first;
location[0] = f;
stype[0] = 0;
if (n == 1) return;
int mn = 1;
for (int i = 1; i < n; i++)
if (get(0, i) < get(0, mn))
mn = i;
vector<int> P[2];
for (int i = 0; i < n; i++) {
if (i == 0 || i == mn) continue;
P[int(get(0, i) == get(0, mn) + get(mn, i))].push_back(i);
}
P[0].push_back(mn);
P[1].push_back(0);
location[mn] = location[0] + get(0, mn);
stype[mn] = 1;
solve(0, P[0]);
solve(mn, P[1]);
for (int e : P[0]) {
if (e != 0 && e != mn) {
location[e] = location[0] + pos[e];
stype[e] = stype[0] ^ TTop[e];
}
}
for (int e : P[1]) {
if (e != 0 && e != mn) {
location[e] = location[mn] - pos[e];
stype[e] = stype[mn] ^ TTop[e];
}
}
for (int i = 0; i < n; i++)
stype[i]++;
/*
for (int i = 0; i < n; i++) cerr << location[i] << sep;
cerr << endl;
for (int i = 0; i < n; i++) cerr << stype[i] << sep;
cerr << endl;
*/
}
// mn location
