#include "stations.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
namespace{
vector<vector<int>> graph;
vector<int> in, dep, out;
int cnt = 0;
const int inf = 1e9;
void dfs(int node, int parent){
in[node] = cnt;
dep[node] = dep[parent] + 1;
cnt++;
for(auto &x: graph[node]){
if(x != parent) dfs(x, node);
}
out[node] = cnt;
cnt++;
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
vector<int>().swap(in);
vector<int>().swap(dep);
vector<int>().swap(out);
vector<vector<int>>().swap(graph);
in.resize(n);
graph.resize(n);
out.resize(n);
dep.resize(n);
cnt = 0;
for(int i = 0; i < n - 1; i++){
graph[u[i]].push_back(v[i]);
graph[v[i]].push_back(u[i]);
}
dfs(0, 0);
vector<int> ret(n);
for(int i = 0; i < n; i++){
if(dep[i] & 1) ret[i] = in[i];
else ret[i] = out[i];
}
return ret;
}
int find_next_station(int s, int t, std::vector<int> c){
int sz = (int)c.size();
if(s < c[0]){
int l = s + 1;
for(int i = 0; i < sz - 1; i++){
int r = c[i];
if(l <= t && t <= r) return c[i];
l = c[i] + 1;
}
return c[sz - 1];
}
else{
reverse(c.begin(), c.end());
int r = s - 1;
for(int i = 0; i < sz - 1; i++){
int l = c[i];
if(l <= t && t <= r) return c[i];
r = c[i] - 1;
}
return c[sz - 1];
}
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g stations.cpp stub.cpp
