#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi20/d2/debug.h"
#else
#define debug(...) void(37)
#endif
std::vector<int> label(int N, int k, std::vector<int> U, std::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]);
}
debug(g);
vector<int> label(N), d(N, -1);
int t = 0;
function<void(int)> Dfs = [&](int v) {
if (d[v] % 2 == 0) {
label[v] = t++;
}
for (auto u : g[v]) {
if (d[u] == -1) {
d[u] = d[v] + 1;
Dfs(u);
}
}
if (d[v] % 2 == 1) {
label[v] = t++;
}
};
d[0] = 0;
Dfs(0);
return label;
}
int find_next_station(int S, int T, std::vector<int> C) {
debug(S, T, C);
if (S >= C.back()) {
if (T > S || T < C[0]) {
return C[0];
}
return C[int(lower_bound(C.begin(), C.end(), T + 1) - C.begin()) - 1];
} else {
if (T < S || T > C.back()) {
return C.back();
}
return C[int(lower_bound(C.begin(), C.end(), T) - C.begin())];
}
}
