#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
vvi adj(n);
for (int i = 0; i < n-1; i++) adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
vi ret(n);
int t = 0;
auto dfs = [&](auto dfs, int u = 0, int p = 0, int d = 0) -> void {
if (d%2 == 1) ret[u] = t++;
for (int v : adj[u]) if (v != p) dfs(dfs, v, u, d+1);
if (d%2 == 0) ret[u] = t++;
};
dfs(dfs);
return ret;
}
int find_next_station(int s, int t, std::vector<int> c) {
//cout << s << " -> " << t << endl;
//for (int x : c) cout << x << " "; cout << endl;
if (c.size() == 1) return c[0];
sort(c.begin(), c.end());
if (c[0] > s) {
int l = s, r = c[c.size()-2];
if (t < l || t > r) return c.back();
return *lower_bound(c.begin(), c.end(), t);
}
reverse(c.begin(), c.end());
for (int &x : c) x = -x;
int l = c[1], r = s;
if (t < l || t > r) return -c.back();
return -*lower_bound(c.begin(), c.end(), -t);
}
