#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>label(n), h(n);
vector<vector<int>>e(n);
for(int i = 0; i + 1 < n; i++){
e[u[i]].emplace_back(v[i]);
e[v[i]].emplace_back(u[i]);
}
function<void(int, int)>dfs;
int time_dfs = 0;
dfs = [&] (int s, int p){
if(~h[s] & 1){
label[s] = time_dfs++;
}
for(int& d : e[s]){
if(d != p){
h[d] = h[s] + 1;
dfs(d, s);
}
}
if(h[s] & 1){
label[s] = time_dfs++;
}
};
dfs(h[0] = 0, -1);
return label;
}
int find_next_station(int s, int t, vector<int>c) {
if(c.size() == 1){
return c[0];
}
auto it = lower_bound(c.begin(), c.end(), t);
if(it != c.end() && *it == t){
return t;
}
if(s < c[0]){
return s < t && c[int(c.size()) - 2] > t ? *it : c.back();
}
return t < s && t > c[0] ? *prev(it) : c[0];
}
