#include "stations.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)x.size()
using namespace std;
vector<int> a;
vector<bool> ismin;
vector<vector<int>> adj;
int cnt=1;
pair<int, int> dfs(int u, int p=-1, bool mini=1) {
if (sz(adj[u])==1 && p!=-1) {
a[u]=10000*(cnt++);
ismin[u]=mini;
return {a[u], a[u]};
}
a[u]=0;
if (mini) a[u]=INT_MAX;
pair<int, int> bests={INT_MAX, 0};
for (auto &v: adj[u]) if (v!=p) {
auto [mn, mx]=dfs(v, u, mini^1);
cmin(bests.fi, mn), cmax(bests.se, mx);
}
if (mini) a[u]=bests.fi-1, bests.fi=a[u];
else a[u]=bests.se+1, bests.se=a[u];
return bests;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
adj.clear(), adj.resize(n);
for (int i=0; i<n-1; i++) adj[u[i]].pb(v[i]), adj[v[i]].pb(u[i]);
cnt=1, a.clear(), a.resize(n, -1), ismin.clear(), ismin.resize(n, 0);
dfs(0);
vector<int> b=a; sort(all(b));
map<int, int> mp;
for (int i=0; i<n; i++) mp[b[i]]=i;
for (int i=0; i<n; i++) a[i]=mp[a[i]];
return a;
}
int find_next_station(int s, int t, vector<int> c) {
if (sz(c)==1) return c[0];
bool smax=0;
if (*max_element(all(c))<s) smax=1;
if (!smax) { // s: min
if (t<s) return *max_element(all(c));
int best=*max_element(all(c));
for (auto u: c) if (t<=u) {
cmin(best, u);
}
return best;
} else { // s: max
if (t>s) return *min_element(all(c));
int best=*min_element(all(c));
for (auto u: c) if (t>=u) {
cmax(best, u);
}
return best;
}
}
