#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
void make_labels(int p, int par, bool is_max, vector<int>&labels, vector<vector<int>>&adj, int& next_number)
{
if (!is_max) labels[p] = next_number++;
for (int i : adj[p])
{
if (i == par) continue;
make_labels(i, p, !is_max, labels, adj, next_number);
}
if (is_max) labels[p] = next_number++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
vector<vector<int>> adj(n, vector<int>());
for (int i = 0; i < n - 1; i++)
{
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<int> labels(n);
int next_number = 0;
make_labels(0, -1, true, labels, adj, next_number);
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if (s > c[0])
{
if (t > s) return c.front();
if (t <= c.front()) return c.front();
if (upper_bound(c.begin(), c.end(), t) == c.begin()) return c[0];
return *prev(upper_bound(c.begin(), c.end(), t));
} else {
if (t < s) return c.back();
if (t >= c.back()) return c.back();
if (lower_bound(c.begin(), c.end(), t) == c.end()) return c[0];
// assert(lower_bound(c.begin(), c.end(), t) != c.end());
return *lower_bound(c.begin(), c.end(), t);
}
}
