#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
#include "stations.h"
vector<int>g[1001], labels;
int t = 0;
void dfs(int u,int p,bool entrada){
if(entrada){
labels[u] = t++;
}
for(auto v:g[u]){
if(v==p)continue;
dfs(v,u,entrada^1);
}
if(!entrada){
labels[u] = t++;
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
for(int i=0;i<n;++i){
g[i].clear();
}
t = 0;
for(int i=0;i<n-1;++i){
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
labels.resize(n);
dfs(0,0,1);
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int m = sz(c), idx = lower_bound(all(c),t)-begin(c);
if(idx<m&&c[idx]==t)return t;//sou vizinho
if(s>c[m-1]){//sou uma saida
if(t>s||t<c[0])return c[0];//fora da subarvore
return c[lower_bound(all(c),t) - begin(c) - 1];//ultimo cara que é menor
}else{//sou uma entrada
if(t>c[m-1]||t<s)return c[m-1];//fora da subarvore
return c[lower_bound(all(c),t) - begin(c)];//primeiro cara que é maior
}
}
// int main(){_
// int n;cin>>n;
// vector<int>u(n-1),v(n-1);
// for(int i=0;i<n-1;++i){
// cin>>u[i]>>v[i];
// }
// vector<int>labels = label(n,n-1,u,v);
// // for(int i=1;i<=n;++i)printf("%d: %d\n",i-1,labels[i-1]);
// cout<<find_next_station(1,3,{2,4})<<endl;
// }
