#include "stations.h"
#include <algorithm>
using namespace std;
using vi = vector<int>;
int n, c;
vector<int> adj[1000], res;
void dfs(int d=0, int s=0, int e=-1) {
if (d&1) res[s] = c++;
for (const auto &u : adj[s]) if (u != e) dfs(d+1,u,s);
if (~d&1) res[s] = c++;
}
vi label(int _n, int k, vi u, vi v) {
n = _n;
for (int i = 0; i < n-1; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
c=0, res.resize(n), dfs();
for (int i = 0; i < n; ++i) adj[i].clear();
return res;
}
int find_next_station(int s, int t, vi c) {
bool flag = s > c[0];
if (flag) reverse(begin(c),end(c));
int x, y = s;
for (const auto &u : c) {
x = y, y = u;
if (flag) { if (y <= t and t < x) return u; }
else { if (x < t and t <= y) return u; }
}
return c.back();
}
