#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1011;
vector<int> g[MAXN];
int ID[MAXN], tin[MAXN], tout[MAXN], timer = 0;
void dfs(int v, int p, int dep){
tin[v] = timer++;
for (int u : g[v]){
if (u != p) dfs(u, v, dep + 1);
}
tout[v] = timer++;
ID[v] = (dep & 1 ? tin[v] : tout[v]);
}
bool line = true, binary = true;
vector<int> label(int n, int k, vector<int> U, vector<int> V) {
for (int i = 0; i < n; i++) g[i].clear();
timer = 0;
for (int i = 0; i < n - 1; i++){
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
}
dfs(0, -1, 1);
vector<int> labels(n, 0);
for (int i = 0; i < n; i++){
ID[i] /= 2;
labels[i] = ID[i];
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int sz = c.size();
if (sz == 1) return c.back();
if (c.front() > s){ // dep = odd
int lf = s, rg = c[sz - 2];
if (lf > t || rg < t) return c.back();
int pos = lower_bound(c.begin(), c.end(), t) - c.begin();
return c[pos];
} else { // dep = even
int lf = c[1], rg = s;
if (lf > t || rg < t) return c.front();
int pos = upper_bound(c.begin(), c.end(), t) - c.begin() - 1;
return c[pos];
}
return c[0];
}
