#include "stations.h"
#include <bits/stdc++.h>
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>
using namespace std;
static void dfs(int i, int p, int d, int& timer, vector<vector<int>>& adj, vector<int>& l) {
if (!(d & 1))
l[i] = timer++;
for (int& k : adj[i]) {
if (k != p)
dfs(k, i, d+1, timer, adj, l);
}
if (d & 1)
l[i] += timer++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<vector<int>> adj (n);
vector<int> l (n);
range(i, 0, n-1) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int timer = 0;
dfs(0, 0, 0, timer, adj, l);
return l;
}
int find_next_station(int s, int t, vector<int> c) {
// CASE 1 -> s has an 'in' value
// every node in c has value 'out'
// the parent of them all is the right-most value
// s is the left-most value
if (s < c[0]) {
// CASE 1.1 -> t is not a decendant of s
// and t is before s
if ((t < s || c.size() == 1 || t > c[c.size() - 2]) && s != 0)
return c.back();
// CASE 1.2 -> t may or not be decendant of s
// ancestor of t is the first in c that is >= t
return *lower_bound(all(c), t);
}
// CASE 2 -> s has an 'out' value
// every node in c has value 'in'
// the parent of them all is the left-most value
// s is the right-most value
// CASE 2.1 -> t is not a decendant of s
// and t is after s
if (t > s || c.size() == 1 || t < c[1])
return c[0];
// CASE 2.2 -> t may or not be a decendant of s
// ancestor of t is the first in c that is <= t (backwards)
return *(--upper_bound(all(c), t));
}
