#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
vector<int> label(int n, int, vector<int> u, vector<int> v) {
vector<vector<int> > edges(n);
for (int i = 0; i < n - 1; i++) {
edges[u[i]].emplace_back(v[i]);
edges[v[i]].emplace_back(u[i]);
}
vector<int> res(n);
stack<tuple<int,int,bool,bool>> st;
st.emplace(0,0,false,false);
int time = 0;
while (st.size()) {
auto [cur,prev,m,re] = st.top();
st.pop();
if (!m)
res[cur] = time++;
else {
if (re) {
res[cur] = time++;
continue;
}
st.emplace(cur,prev,m,true);
}
for (int edge : edges[cur]) if (edge != prev) st.emplace(edge,cur,!m,false);
}
return res;
}
int find_next_station(int s, int t, vector<int> c) {
if (s < c[0]) {
if (t >= c.back() || t < s)
return c.back();
return *ranges::lower_bound(c, t);
}
if (t > s || t <= c[0])
return c[0];
int lo=0,hi=c.size();
while (hi-lo > 1) {
int mid = (lo+hi)/2;
if (c[mid] > t)
hi = mid;
else
lo = mid;
}
if (hi != c.size() and c[hi] <= t)
return c[hi];
return c[lo];
}
#if 0
int main() {
int n;
cin >> n;
vector<int> edge1(n), edge2(n);
for (int i = 0; i < n - 1; i++) {
cin >> edge1[i] >> edge2[i];
}
auto labels = label(n, 0, edge1, edge2);
map<int, int> mapping;
for (int i = 0; i < n; i++)
mapping[labels[i]] = i;
assert(mapping.size() == n);
for (auto [map,mapped]: mapping)
println("{}, {}", map, mapped);
int i,j;
cin >> i >> j;
int currentIndex = i;
while (currentIndex != j) {
vector<int> values;
if (mapping[currentIndex] != 0)
values.emplace_back(labels[mapping[currentIndex] - 1]);
if (mapping[currentIndex] != n - 1)
values.emplace_back(labels[mapping[currentIndex] + 1]);
ranges::sort(values);
currentIndex = find_next_station(currentIndex, j, values);
cout << currentIndex << '\n';
}
}
#endif
