#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > adj;
vector<int> val;
int timer_ = 0;
void dfs(int u, int p, int depth){
if(depth % 2 == 0){
val[u] = timer_++;
}
for(int v : adj[u]){
if(v != p){
dfs(v, u, depth + 1);
}
}
if(depth % 2 == 1){
val[u] = timer_++;
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
adj.assign(n, vector<int>());
val.assign(n, 0);
timer_ = 0;
for(int i = 0; i < n - 1; i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, -1, 0);
adj.clear();
return val;
}
int find_next_station(int s, int t, vector<int> c){
sort(c.begin(), c.end());
if(c.empty()){
return s;
}
if(c[0] > s){
int last = s;
for(int x : c){
if(last < t && t <= x){
return x;
}
last = x;
}
return c.back();
}
else{
for(int i = 0; i < (int)c.size(); i++){
int nxt;
if(i + 1 < (int)c.size()){
nxt = c[i + 1];
}
else{
nxt = s;
}
if(c[i] <= t && t < nxt){
return c[i];
}
}
return c[0];
}
}
