#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <int> > g;
int cnt;
vector <int> labels;
void dfs (int x, int fa, bool b) {
if (b) labels[x] = cnt ++;
for (int t : g[x]) {
if (t == fa) continue;
dfs (t, x, ! b);
}
if (! b) labels[x] = cnt ++;
}
vector <int> label (int n, int k, vector <int> u, vector<int> v) {
cnt = 0;
g.clear (), g.resize (n);
for (int i = 0; i < n - 1; i++) g[u[i]].push_back (v[i]), g[v[i]].push_back (u[i]);
labels.assign (n, -1);
dfs (0, -1, true);
return labels;
}
int find_next_station (int s, int t, vector <int> c) {
int n = (int) c.size ();
if (s < c[0]) {
if (t < s) return c[n - 1];
for (int i = 0; i < n - 1; i ++) {
if (t <= c[i]) return c[i];
}
return c[n - 1];
} else {
if (t > s) return c[0];
for (int i = n - 1; i > 0; i --) {
if (c[i] <= t) return c[i];
}
return c[0];
}
}
