#include "stations.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
vector <ll> adj[1000];
ll sz[1000], A[1000];
void dfs(ll u, ll p) {
++sz[u];
for (auto v : adj[u]) {
if (v != p) {
dfs(v, u);
sz[u] += sz[v];
}
}
}
void solve(ll u, ll p, ll l, ll r, ll d) {
if (!d) A[u] = l++;
else A[u] = r--;
for (auto v : adj[u]) {
if (v != p) {
solve(v, u, l, l+sz[v]-1, d^1);
l += sz[v];
}
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
for (int i=0; i<n-1; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, -1);
solve(0, -1, 0, n-1, 0);
vector <int> L(n);
for (int i=0; i<n; ++i) {
L[i] = A[i];
}
return L;
}
int find_next_station(int s, int t, std::vector<int> c) {
sort(c.begin(), c.end());
ll mn = s, mx = s;
for (auto u : c) {
mn = min(mn, (ll)u);
mx = max(mx, (ll)u);
}
if (t < mn || mx > t) {
if (mn == s) return mx;
else return mn;
}
else {
if (mn == s) {
auto it = lower_bound(c.begin(), c.end(), t);
return *it;
}
else {
auto it = prev(lower_bound(c.begin(), c.end(), t+1));
return *it;
}
}
}
