#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 1001;
int timer, stt[MXN], fnt[MXN], h[MXN];
vector<int> g[MXN];
void dfs(int v, int p=-1) {
stt[v] = timer++;
for(int u : g[v])
if(u!=p) {
h[u] = h[v]^1;
dfs(u, v);
}
fnt[v] = timer++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
for(int i=0; i<n; i++) g[i].clear();
timer = 0;
for(int i=0; i<n-1; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs(0);
vector<int> ans(n);
vector<int> cmp;
for(int i=0; i<n; i++)
cmp.push_back((h[i]&1) ? fnt[i] : stt[i]);
sort(cmp.begin(), cmp.end());
auto GI = [&](int x) {
return lower_bound(cmp.begin(), cmp.end(), x)-cmp.begin();
};
for(int i=0; i<n; i++)
ans[i] = GI((h[i]&1) ? fnt[i] : stt[i]);
return ans;
}
int find_next_station(int s, int t, vector<int> c) {
if(c.size()==1) return c[0];
if(s<c[0]) { // stt s
int fn = c[c.size()-2];
if(s <= t && t <= fn) {
for(int i : c)
if(i>=t)
return i;
}
return c.back();
}
else { // fnt s
int st = c[1]-1;
if(st <= t && t <= s) {
for(int i=c.size()-1; i>=0; i--)
if(c[i]<=t)
return c[i];
}
return c[0];
}
}
