#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 5050;
int dis[mxn][mxn];
int idx[mxn], lvl[mxn];
vector<int> adj[mxn];
void dfs(int u, int p = 0) {
lvl[u] = lvl[p] ^ 1;
for(int v : adj[u])
if(v != p) {
if(lvl[u] & 1) idx[v] = idx[u] - dis[u][v];
else idx[v] = idx[u] + dis[u][v];
dfs(v, u);
}
}
void findLocation(int n, int st, int x[], int t[]) {
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
dis[i][j] = dis[j][i] = getDistance(i, j);
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
for(int k = 0; k < n; k++)
if(dis[i][j] == dis[i][k] + dis[k][j]) {
adj[i].push_back(j);
adj[j].push_back(i);
}
lvl[0] = 1;
dfs(0);
for(int i = 0; i < n; i++) {
t[i] = lvl[i] + 1;
x[i] = idx[i];
}
}
