#include <bits/stdc++.h>
#include "stations.h"
// #include "stub.cpp"
using namespace std;
const int N = 1e3 + 10;
int sz[N];
vector<int> res, g[N];
void dfs(int v, int p = -1){
sz[v] = 1;
for (int u : g[v]){
if (u == p) continue;
dfs(u, v);
sz[v] += sz[u];
}
}
void assign(int v, int l = 1, int p = -1, int dist = 0){
if (dist % 2 == 0)
res[v] = l + sz[v] - 1;
else
res[v] = l;
// cout << v << " : " << res[v] << endl;
int prv = 0;
for (int u : g[v]){
if (u == p) continue;
assign(u, l + (res[v] == l) + prv, v, dist + 1);
prv += sz[u];
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
res.resize(n);
for (int i = 0; i < n; i ++) g[i].clear();
for (int i = 0; i < n - 1; i ++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs(0);
assign(0);
return res;
}
int find_next_station(int s, int t, vector<int> c) {
if (c.size() == 1) return c[0];
if (s < c[0]){ // I am the one who says everyone in subtree is >= s
if (t < s or t > c[c.size() - 2]) return c.back();
return *lower_bound(c.begin(), c.end(), t);
}
else{ // <= s
if (t > s or t < c[1]) return c[0];
return c[upper_bound(c.begin(), c.end(), t) - c.begin() - 1];
}
}
