#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
vector<int> label(int n,int k,vector<int> a,vector<int> b){
vvi g(n);
rep(i,n-1){
g[a[i]].pb(b[i]);g[b[i]].pb(a[i]);
}
vp dp(n);
dp[0]=P(0,n-1);
vector<int> res(n);
vi sub(n,1);
function<ll(ll,ll)> dfs0=[&](ll i,ll p){
for(ll x:g[i])if(x!=p)sub[i]+=dfs0(x,i);
return sub[i];
};dfs0(0,-1);
function<void(ll,ll,ll)> dfs1=[&](ll i,ll p,ll d){
if(d%2)res[i]=dp[i].fi++;
else res[i]=dp[i].se--;
for(ll x:g[i])if(x!=p){
dp[x]=P(dp[i].fi,dp[i].fi+sub[x]-1);
dp[i].fi+=sub[x];
dfs1(x,i,d+1);
}
};dfs1(0,-1,0);
return res;
}
int find_next_station(int s,int t,vector<int> c){
for(int x:c)if(x==t)return t;
if(c.size()==1)return c[0];
if(s<c[0]){
if(t<s||t>c.back())return c.back();
rep(i,c.size())if(c[i]>t)return c[i];
}
if(t>s||t<c[0])return c[0];
for(int i=c.size()-1;i>=0;i--)if(c[i]<t)return c[i];
}
