#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct tree {
int n;
vi sz;
vector<vi> L;
tree(int N) : n(N), sz(N, 1), L(N) {}
void add_edge(int u, int v) {
L[u].push_back(v);
L[v].push_back(u);
}
vi get_labels() {
function<void(int, int)> dfs0 = [&](int u, int p) {
sz[u] = 1;
for(auto it : L[u]) {
if(it == p) continue;
dfs0(it, u);
sz[u] += sz[it];
}
};
dfs0(0, -1);
vi Re(n, -1);
function<void(int, int, int, int, int)> dfs =
[&](int u, int p, int l, int r, int tip) {
if(tip) {
Re[u] = l;
int v = l + 1;
for(auto it : L[u]) {
if(it == p) continue;
dfs(it, u, v, v + sz[it] - 1, tip ^ 1);
v += sz[it];
}
} else {
Re[u] = r;
int v = r - 1;
for(auto it : L[u]) {
if(it == p) continue;
dfs(it, u, v - sz[it] + 1, v, tip ^ 1);
v -= sz[it];
}
}
};
dfs(0, -1, 0, n - 1, 0);
// printf("Labels: ");
// for(auto it : Re) printf("%d ", it);
// printf("\n");
return Re;
}
};
vi label(int n, int k, vi u, vi v) {
tree T(n);
for(int i = 0; i + 1 < n; ++i)
T.add_edge(u[i], v[i]);
return T.get_labels();
}
int find_next_station(int s, int t, vi c) {
int tip = 0;
for(auto it : c) {
if(it < s) tip = 1;
}
sort(c.begin(), c.end());
if(!tip) { /// toti din jur sunt mai mari
if(t < s || t >= c.back()) return c.back();
for(auto it : c) {
if(t <= it) return it;
}
} else { // toti din jur sunt mai mici
if(t > s || t <= c[0]) return c[0];
reverse(c.begin(), c.end());
for(auto it : c)
if(t >= it) return it;
}
}
