#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[5010];
struct UF
{
int rep[5010];
UF()
{
for (int i = 0; i < 5010; i++) rep[i] = i;
}
int findrep(int a)
{
if (rep[a] == a) return a;
return rep[a] = findrep(rep[a]);
}
void merge(int a, int b)
{
rep[findrep(a)] = findrep(b);
}
};
UF uf;
int ty[5010];
int seen[5010];
int loc[5010];
int dis[5010][5010];
void dfs(int a, int d, int type = 0)
{
if (seen[a]) return;
seen[a] = 1;
ty[a] = type;
loc[a] = d;
for (int b : adj[a])
{
int newd = d;
if (type) newd -= dis[a][b];
else newd += dis[a][b];
dfs(b, newd, !type);
}
}
void findLocation(int n, int first, int location[], int stype[])
{
vector<pair<int, pair<int, int> > > edges;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
int d = getDistance(i, j);
edges.emplace_back(d, make_pair(i, j));
dis[i][j] = dis[j][i] = d;
}
}
sort(edges.begin(), edges.end());
for (auto a : edges)
{
int u = a.second.first;
int v = a.second.second;
if (uf.findrep(u) != uf.findrep(v))
{
uf.merge(u, v);
adj[u].push_back(v);
adj[v].push_back(u);
}
}
dfs(0, first);
for (int i = 0; i < n; i++) stype[i] = ty[i]+1;
for (int i = 0; i < n; i++) location[i] = loc[i];
}
