#include "stations.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int MXN = 1010;
constexpr static int LOWER_BOUND = 0;
constexpr static int UPPER_BOUND = 1;
vector<int> labels, g[MXN];
int nxt;
void dfs(int node, int parent, int state)
{
if (state == LOWER_BOUND)
labels[node] = nxt++;
for (int c : g[node])
if (c != parent)
dfs(c, node, state^1);
if (state == UPPER_BOUND)
labels[node] = nxt++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
labels = vector<int>(n);
for (int i = 0; i < n; i++)
g[i].clear();
for (int i = 0; i < n-1; i++)
{
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
nxt = 0;
dfs(0, 0, LOWER_BOUND);
return labels;
}
int find_next_station(int s, int t, vector<int> c)
{
debug(s, t, c);
assert(!c.empty());
int state;
int lb, ub, parent;
if (s > c[0]) // Upper Bound
{
state = UPPER_BOUND;
parent = c[0];
lb = parent; // Parent
ub = s;
}
else
{
state = LOWER_BOUND;
parent = c.back();
lb = s;
ub = parent; // Parent
}
if (t > ub || lb > t)
return parent;
auto it = upper_bound(c.begin(), c.end(), t);
if (state == UPPER_BOUND)
it--;
return *it;
}
