#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e3+5;
int in[nx], out[nx], cnt, pa;
vector<int> res, d[nx];
void dfs(int u, int p)
{
in[u]=++cnt;
for (auto v:d[u]) if (v!=p) dfs(v, u);
out[u]=cnt;
}
int getin(int x)
{
return x/1000;
}
int getout(int x)
{
return x%1000;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
cnt=-1;
for (int i=0; i<n; i++) d[i].clear();
res.resize(n);
for (int i=0; i<n-1; i++) d[u[i]].push_back(v[i]), d[v[i]].push_back(u[i]);
dfs(0, 0);
for (int i=0; i<n; i++) res[i]=1000*in[i]+out[i];
return res;
}
int find_next_station(int s, int t, std::vector<int> c) {
for (auto x:c) if (getin(x)<=getin(s)&&getout(s)<=getout(x)) pa=x;
for (auto x:c) if (x!=pa&&getin(x)<=getin(t)&&getout(t)<=getout(x)) return x;
return pa;
}
