#include <bits/stdc++.h>
#include <stations.h>
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
int t = -1;
vector<vector<int>> G(n);
vector<int> sol(n);
for (int i = 0; i < n - 1; ++i) {
G[u[i]].emplace_back(v[i]);
G[v[i]].emplace_back(u[i]);
}
function<void(int, int, int)> dfs = [&](int node, int last, int lvl) {
if (!lvl)
sol[node] = ++t;
for (auto x : G[node])
if (x != last)
dfs(x, node, lvl ^ 1);
if (lvl)
sol[node] = ++t;
};
dfs(0, -1, 0);
return sol;
}
int find_next_station(int s, int f, vector<int> adj) {
int tins, touts, ft,mini=INT_MAX,maxi=0;
int isin = 1;
for (auto x : adj) {
if (x < s)
isin = 0;
mini = min(mini, x);
maxi = max(maxi, x);
}
if (isin)
tins = s, ft = maxi, touts = ft - 1;
else
touts = s, ft = mini, tins = ft + 1;
//cerr << ft << '\n';
if (tins <= f && f <= touts) {
int last = s;
if (isin)
sort(adj.begin(), adj.end());
else
sort(adj.begin(), adj.end(), greater<int>());
for (auto x : adj)
if (x != ft) {
int curtin, curtout;
if (isin)
curtout = x, curtin = last + 1, last = x;
else
curtin = x, curtout = last - 1, last = x;
//cerr << curtin << ' ' << curtout << '\n';
if (curtin <= f && f <= curtout)
return x;
}
}
return ft;
}
