#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> label(int n, int k,vector<int> a, vector<int> b) {
int t=0;
vector<int> disc, v(n, -1),in(n, -1), out(n, -1), dep(n, 0);
vector<vector<int>> al(n);
auto dfs = [&](auto dfs, int x, int p)->void{
in[x]=t++;
for(auto to:al[x]){
if(to==p)continue;
dep[to]=dep[x]+1;
dfs(dfs, to,x);
}
out[x]=t++;
if(dep[x]%2==0)v[x]=in[x];
else v[x]=out[x];
disc.push_back(v[x]);
//~ printf("at %lld, in %lld out %lld v[x] %lld\n", x, in[x], out[x], v[x]);
};
for(int i=0;i<n-1;i++){
al[b[i]].push_back(a[i]);
al[a[i]].push_back(b[i]);
}
dfs(dfs, 0, -1);
//~ for(int i=0;i<n;i++){
//~ cout<<in[i]<<" "<<out[i]<<" : " << v[i]<<endl;
//~ }
sort(disc.begin(),disc.end());
for(int i=0;i<n;i++){
v[i]=lower_bound(disc.begin(),disc.end(),v[i])-disc.begin();
}
vector<int> labels(n);
for (int i = 0; i < n; i++) {
labels[i] = v[i];
//~ printf("index %d has label %d\n", i, labels[i]);
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int sz=c.size();
assert((s <= c[0]) ^ (s >= c[sz-1]));
int ret=-1;
if(sz==1){
ret=c[0];
}
else if(s<=c[0]){
for(int i=0;i<sz;i++){
if(t>=s and t <= c[i]){
ret=c[i];
break;
}
ret=c[i];
}
}
else {
for(int i=sz-1;i>=0;i--){
if(t <= s and t >= c[i]){
ret=c[i];
break;
}
ret=c[i];
}
}
//~ printf("query %d to %d, returning %d\n", s,t,ret);
return ret;
}
