#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
vector<vector<int>> adj(n);
for (int i = 0; i + 1 < n; i++) {
adj[u[i]].emplace_back(v[i]);
adj[v[i]].emplace_back(u[i]);
}
vector<int> st(n), et(n);
int timer = 0;
const function<void(int, int, int)> Dfs = [&](int u, int p, int odd) {
st[u] = timer++;
for (auto v : adj[u]) if (v != p) {
Dfs(v, u, odd ^ 1);
}
et[u] = timer++;
if (odd) {
labels[u] = st[u];
} else {
labels[u] = et[u];
}
};
Dfs(0, -1, 0);
vector<int> coords = labels;
sort(begin(coords), end(coords));
for (int i = 0; i < n; i++) {
labels[i] = lower_bound(begin(coords), end(coords), labels[i]) - begin(coords);
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
if (s < *min_element(begin(c), end(c))) {
int par = c.back();
for (auto u : c) {
if (u != par && s <= t && t <= u) {
return u;
}
}
return par;
} else {
reverse(begin(c), end(c));
int par = c.back();
for (auto u : c) {
if (u != par && u <= t && t <= s) {
return u;
}
}
return par;
}
}
