#include "stations.h"
#include <bits/stdc++.h>
#include <vector>
int timer = 0;
using namespace std;
vector < vector <int> > Adj;
vector <int> tin,tout,depth;
void PREP(int n) {
Adj.clear();
tin.clear();
tout.clear();
depth.clear();
Adj.resize(n);
tin.resize(n);
tout.resize(n);
depth.resize(n);
depth[1] = 0;
timer = 1;
}
void DFS(int v,int p) {
tin[v] = timer;
timer++;
for (int x : Adj[v]) {
if (x == p) continue;
DFS(x,v);
depth[x] = depth[v] + 1;
}
tout[v] = timer;
timer++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
vector <int> labels(n);
PREP(n);
for (int i = 0;i < n-1;i++) {
int a = u[i];
int b = v[i];
Adj[a].push_back(b);
Adj[b].push_back(a);
}
DFS(1,-1);
for (int i = 0; i < n; i++) {
labels[i] = depth[i] % 2 == 0 ? tin[i] / 2 : tout[i] / 2;
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if (s < c[0]) {
if (t < s || c.size() == 1 || t > c[c.size() - 2])
return c.back();
return *lower_bound(c.begin(), c.end(), t);
} else {
if (t > s || c.size() == 1 || t < c[1])
return c[0];
return *(upper_bound(c.begin(), c.end(), t) - 1);
}
}
