#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<vector<int>> g(n);
for (int i = 0; i + 1 < n; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
vector<int> tin(n), tout(n), lab(n);
int T = 0;
function<void(int, int, int)> Dfs = [&](int v, int pv, int d) {
if (d % 2 == 0) {
lab[v] = ++T;
}
for (int u : g[v]) {
if (u == pv) {
continue;
}
Dfs(u, v, d ^ 1);
}
if (d % 2 == 1) {
lab[v] = ++T;
}
};
Dfs(0, 0, 0);
return lab;
}
int find_next_station(int s, int t, vector<int> c) {
int n = (int) c.size();
if (n == 1) {
return c[0];
}
for (int i = 0; i < n; i++) {
if (c[i] == t) {
return c[i];
}
}
for (int i = 0; i < n; i++) {
assert(s != c[i]);
}
if (s < c[0]) {
if (t >= s && t <= c[0]) {
return c[0];
}
for (int i = 1; i + 1 < n; i++) {
if (t > c[i - 1] && t <= c[i]) {
return c[i];
}
}
return c[n - 1];
} else {
assert(s > c[n - 1]);
if (t >= c[n - 1] && t <= s) {
return c[n - 1];
}
for (int i = n - 2; i > 0; i--) {
if (t >= c[i] && t < c[i + 1]) {
return c[i];
}
}
return c[0];
}
}
