#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> graf[100005];
vector <int> labels;
int in[100005];
int out[100005];
int tajm;
void dfs(int v, int depth, int par){
in[v] = ++tajm;
for(auto c : graf[v]){
if(c != par){
dfs(c, depth+1, v);
}
}
out[v] = ++tajm;
if(depth%2){
labels[v] = out[v];
}
else labels[v] = in[v];
}
map <int, int> koji;
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
labels.clear();
labels.resize(n);
for(int i=0; i<n; i++){
graf[i].clear();
in[i] = 0;
out[i] = 0;
}
for(int i=0; i<n-1; i++){
graf[u[i]].push_back(v[i]);
graf[v[i]].push_back(u[i]);
}
dfs(0, 0, -1);
int tr = -1;
vector <int> vec;
for(auto c : labels) vec.push_back(c);
sort(vec.begin(), vec.end());
koji.clear();
for(auto c : vec){
koji[c] = ++tr;
}
for(int i=0; i<n; i++) labels[i] = koji[labels[i]];
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(s < c[0]){
///in
if(s == 0){
for(auto g : c) if(g >= t) return g;
}
int aut = c[c.size()-2];
if(s <= t && t <= aut){
for(auto g : c) if(g >= t) return g;
}
return c.back();
}
/// out
int iin = c[1];
if(iin <= t && t <= s){
for(int j=c.size()-1; j>=1; j--){
if(c[j] <= t) return c[j];
}
}
return c[0];
}
