#include<bits/stdc++.h>
using namespace std;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#include "stations.h"
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> dp(n);
vector<vector<int>> adj(n);
L(i,0,n-2){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int tempo=0;
auto dfs=[&](auto&& self, int node,int pai, int tipo)->void{
if(tipo==0){
dp[node]=tempo++;
}
int x=0;
for(auto a:adj[node]){
if(a==pai)continue;
self(self,a,node,tipo^1);
}
if(tipo==1){
dp[node]=tempo++;
}
};
dfs(dfs,0,0,0);
return dp;
}
int find_next_station(int s, int t, std::vector<int> c) {
int n=sz(c);
if(n==1)return c[0];
int tipo=0;
for(auto a:c){
if(a>s)tipo=1;
}
if(tipo==0){//marca tempo de entrada e filhos tempo de saida
if(s==0){
int id=0;
while(c[id]<t)id++;
return c[id];
}
else{
int pai=c.back();
//vejo se ta dentro do s
if(t<s || t>c[n-2])return pai;
int id=0;
while(c[id]<t)id++;
return c[id];
}
}
else{
int pai=c[0];
int id=n-1;
if(t<c[1] || t>s)return pai;
while(c[id]>t)id--;
return c[id];
}
}
