#include <bits/stdc++.h>
#include "stations.h"
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;
#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif
const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;
vector <int> a[mn];
int st[mn], ft[mn], d[mn], timer_dfs = 0;
void dfs(int u, int p) {
st[u] = ++ timer_dfs;
for(auto v : a[u]) {
if(v == p) continue;
d[v] = d[u] + 1;
dfs(v, u);
}
ft[u] = ++ timer_dfs;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
timer_dfs = 0;
for(int i = 0; i < n; i++) {
d[i] = 0;
a[i].clear();
}
for(int i = 0; i < n - 1; i++) {
a[u[i]].push_back(v[i]);
a[v[i]].push_back(u[i]);
}
dfs(0, -1);
vector<int> labels(n);
for (int i = 0; i < n; i++) {
if(d[i] % 2) labels[i] = st[i];
else labels[i] = ft[i];
}
vector <int> comp;
for(int i = 0; i < n; i++) comp.push_back(labels[i]);
sort(all(comp)); comp.erase(unique(all(comp)), comp.end());
for(int i = 0; i < n; i++) labels[i] = lower_bound(all(comp), labels[i]) - comp.begin() + 1;
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(c.size() == 1) return c[0];
sort(all(c));
if(s < c[0]) { // s = st[u]
if(t >= s && t <= c[c.size() - 2]) {
return *(lower_bound(all(c), t));
}
return c[c.size() - 1];
}
else { // s = ft[u]
if(t <= s && t >= c[1]) {
return *(--upper_bound(all(c), t));
}
return c[0];
}
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro
