#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)
vector <int> label(int n, int k, vector <int> u, vector <int> v) {
vector <vector <int> > g(n);
rep(i, n - 1) {
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
vector <int> dfn(n), ed(n), dep(n);
int tme = 0;
function <void(int, int)> dfs;
dfs = [&] (int u, int p) {
dfn[u] = tme ++;
rep(i, g[u].size()) {
int v = g[u][i];
if (v == p) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
ed[u] = tme ++;
};
dfs(0, -1);
vector <int> V;
rep(i, n) V.pb(dep[i] & 1 ? ed[i] : dfn[i]);
sort(V.begin(), V.end());
vector <int> lbl(n);
rep(i, n) lbl[i] = lower_bound(V.begin(), V.end(), dep[i] & 1 ? ed[i] : dfn[i]) - V.begin();
return lbl;
}
int find_next_station(int s, int t, vector <int> c) {
bool dfn_ed = 0;
rep(i, c.size()) dfn_ed |= s > c[i];
if (dfn_ed == 0) {
sort(c.begin(), c.end());
rep(i, c.size() - (s != 0)) {
int dfn = (i ? c[i - 1] : s) + 1, ed = c[i];
if (dfn <= t && t <= ed) return c[i];
}
return c.back();
} else {
sort(c.begin(), c.end());
rep(i, c.size()) if (i) {
int dfn = c[i], ed = (i + 1 < (int) c.size() ? c[i + 1] : s) - 1;
if (dfn <= t && t <= ed) return c[i];
}
return c[0];
}
return -1;
}
#ifdef DEBUG
int main() {
vector <int> lbl = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
cerr << find_next_station(lbl[2], lbl[0], {lbl[1], lbl[4]}) << " " << lbl[1] << endl;
cerr << find_next_station(lbl[1], lbl[3], {lbl[0], lbl[2], lbl[3]}) << " " << lbl[3] << endl;
return 0;
}
#endif
