#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];
ismin[u]=mini;
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]]*2+(1-ismin[i]);
// for (int i=0; i<n; i++) cout << a[i] << ' ';
// cout << endl;
return a;
}
int find_next_station(int s, int t, vector<int> c) {
if (sz(c)==1) return c[0];
// cout << s << ' ' << t << endl;
bool tmax=t%2, smax=s%2; t/=2, s/=2; for (auto &u: c) u/=2;
// cout << s << ' ' << t << ' ' << smax << ' ' << tmax << endl;
if (!tmax && !smax) { // both min
// cout << "OK" << endl;
if (t<s) return *max_element(all(c))*2+1;
int best=*max_element(all(c));
for (auto u: c) if (t<=u) {
cmin(best, u);
}
return best*2+1;
} else if (tmax && smax) { // both max
if (t>s) return *min_element(all(c))*2;
int best=*min_element(all(c));
for (auto u: c) if (t>=u) {
cmax(best, u);
}
return best*2;
} else if (tmax && !smax) { // t: max, s: min
if (t>=*max_element(all(c)) || t<=s) return *max_element(all(c))*2+1;
int best=*max_element(all(c));
for (auto u: c) if (t<=u) {
cmin(best, u);
}
return best*2+1;
} else { // t: min, s: max
if (t<=*min_element(all(c)) || t>=s) return *min_element(all(c))*2;
// int cnt=0;
// for (auto u: c) {
// if (u<=t) cnt++;
// if (u==t) return u*2;
// }
// if (cnt==1) return *min_element(all(c))*2;
int best=*min_element(all(c));
for (auto u: c) if (t>=u) {
cmax(best, u);
}
return best*2;
}
}
