#include<bits/stdc++.h>
#include "stations.h"
using namespace std;
using ll = long long;
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n), subs(n);
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; i++)
adj[u[i]].push_back(v[i]),
adj[v[i]].push_back(u[i]);
auto dfs_s = [&](auto& dfs, int i, int p)->void {
subs[i] = 1;
for (int e : adj[i]) {
if (e != p) {
dfs(dfs, e, i);
subs[i] += subs[e];
}
}
};
dfs_s(dfs_s, 0, -1);
auto dfs = [&](auto& dfs, int i, int p, int dep, int l, int r)->void {
for (int e : adj[i]) {
if (e == p) continue;
int nl, nr;
if (dep % 2 == 0) {
nl = r - subs[e] + 1;
nr = r;
r -= subs[e];
} else {
nl = l;
nr = l + subs[e] - 1;
l += subs[e];
}
dfs(dfs, e, i, dep+1, nl, nr);
}
assert(l == r);
labels[i] = l;
};
dfs(dfs, 0, -1, 0, 0, n-1);
// for (int i : labels) cout << i << ' '; cout << endl;
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
sort(c.begin(), c.end());
if (s == 0) {// root
for (int i : c) {
if (t <= i) return i;
}
assert(false);
}
if (c[0] < s) { // left-right-left
int par = c[0];
if (s < t) return par;
c.erase(c.begin());
reverse(c.begin(), c.end());
for (int j : c) {
if (j <= t) return j;
}
return par;
} else {//right-left-right
reverse(c.begin(), c.end());
int par = c[0];
if (t < s) return par;
c.erase(c.begin());
reverse(c.begin(), c.end());
for (int j : c) {
if (t <= j) return j;
}
return par;
}
}
