#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 < n - 1; i++){
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
}
vector<int> a(n);
int k = 1;
function<void(int, int)> dfs = [&](int u, int anc){
for(int v : g[u]){
if(v == anc){
continue;
}
a[v] = k++;
for(int w : g[v]){
if(w != u){
dfs(w, v);
}
}
}
a[u] = k++;
};
a[0] = 0;
for(int v : g[0]){
dfs(v, 0);
}
return a;
}
int find_next_station(int s, int t, vector<int> c){
int m = (int)c.size();
if(s > c.back()){
for(int i = 1; i < m; i++){
int l = c[i];
int r = i == m - 1 ? s - 1 : c[i + 1] - 1;
if(t >= l && t <= r){
return c[i];
}
}
return c[0];
} else{
for(int i = 0; i < m - 1; i++){
int l = i == 0 ? s + 1 : c[i - 1] + 1;
int r = c[i];
if(t >= l && t <= r){
return c[i];
}
}
return c.back();
}
}
