#include <bits/stdc++.h>
using namespace std;
#include "stations.h"
vector<int> label(int n,int m,vector<int> U,vector<int> V){
vector<vector<int>> G(n);
for (int i(0);i < n-1;++i) G[U[i]].emplace_back(V[i]),G[V[i]].emplace_back(U[i]);
vector<int> R(n),mode(n);
int t(1);
auto dfs = [&](auto& dfs,int x,int p) -> void {
mode[x] = !mode[p];
if (mode[p]) R[x] = t++;
for (int y:G[x]) if (y!=p) dfs(dfs,y,x);
if (mode[x]) R[x] = t++;
};
for (int i:G[0]) dfs(dfs,i,0);
return R;
}
int find_next_station(int s,int g,vector<int> A){
if (s==0) return *lower_bound(A.begin(),A.end(),g);
if (A.size()==1) return A[0];
if (A.size()==2){
if (A[0]<s) return A[(A[1]<=g&&g<=s)];
return A[(g<s||A[0]<g)];
}
if (A[0]>s){
if (s<=g&&g<=A.end()[-2]) return *lower_bound(A.begin(),A.end(),g);
return A.back();
}
if (A[1]<=g&&g<=s) return *prev(upper_bound(A.begin(),A.end(),g));
return A[0];
}
