#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN=1000;
int n, d[mxN], anc[mxN][10];
vector<int> adj[mxN];
void dfs(int u=0) {
for (int i=1; i<10; ++i)
anc[u][i]=anc[anc[u][i-1]][i-1];
for (int v : adj[u])
if (v!=anc[u][0]) {
d[v]=d[u]+1;
anc[v][0]=u;
dfs(v);
}
}
int lca(int u, int v) {
if (d[u]>d[v])
swap(u, v);
for (int i=9; ~i; --i)
if (d[v]-(1<<i)>=d[u])
v=anc[v][i];
if (u==v)
return u;
for (int i=9; ~i; --i)
if (anc[u][i]^anc[v][i])
u=anc[u][i], v=anc[v][i];
return anc[u][0];
}
int dist(int u, int v) {
return d[u]+d[v]-2*d[lca(u, v)];
}
vector<int> label(int _n, int _k, vector<int> u, vector<int> v) {
n=_n;
for (int i=0; i<n; ++i)
adj[i].clear();
for (int i=0; i<n-1; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs();
vector<int> labels(n);
iota(labels.begin(), labels.end(), 0);
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int st=dist(s, t);
//cout << s << " " << t << " " << st << endl;
for (int i : c)
if (dist(s, i)+dist(t, i)==st) {
//cout << i << " " << dist(s, i) << " " << dist(t, i) << endl;
return i;
}
assert(0);
return -1;
}
