// Be name khoda //
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "(" << #x << "):" << x << endl;
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int maxn5 = 1e5 + 10;
vector <int> ret, adj[maxn5];
int h[maxn5], st[maxn5], ft[maxn5], ti;
bool mark[maxn5];
void dfs(int v){
mark[v] = true;
st[v] = ++ti;
for(auto u : adj[v]) if(!mark[u]){
h[u] = h[v] + 1;
dfs(u);
}
ft[v] = ++ti;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
ret.clear();
ret.resize(n);
h[0] = 0;
ti = -1;
fill(mark, mark + n + 4, false);
for(int i = 0; i < n; i++){
adj[i].clear();
}
for(int i = 0; i < n - 1; i++){
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
}
dfs(0);
for(int i = 0; i < n; i++){
if(h[i] & 1)
ret[i] = ft[i];
else
ret[i] = st[i];
}
vector <int> num; num.clear();
for(int i = 0; i < n; i++)
num.pb(ret[i]);
sort(all(num));
num.resize(unique(all(num)) - num.begin());
for(int i = 0; i < n; i++){
ret[i] = lower_bound(all(num), ret[i]) - num.begin();
}
return ret;
}
int find_next_station(int s, int t, std::vector<int> c) {
for(auto u : c) if(u == t)
return t;
sort(all(c));
if(s == 0){
int pt = upper_bound(all(c), t) - c.begin();
return c[pt];
}
if(c.size() == 1)
return c[0];
if(s < c[0]){ // s is st
int st = s, ft = c[int(c.size()) - 2];
if(st > t || ft < t){
return c.back(); // par
}
else{
int pt = upper_bound(all(c), t) - c.begin();
return c[pt];
}
}
else{ // s is ft
int ft = s, st = c[1];
if(st >= t || ft < t)
return c[0];
int pt = upper_bound(all(c), t) - c.begin() - 1;
return c[pt];
}
}
