#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
int t;
vector<tuple<int,int,int>> val;
vector<int> labels;
vector<vector<int>> edges;
void dfs(int x, int pai, int niv) {
t++;
if(niv%2 == 0) labels[x] = t;
for(int viz : edges[x]) if(viz != pai) dfs(viz, x, niv+1);
if(niv%2 == 1) labels[x] = t;
val.pb({labels[x], niv, x});
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
labels.clear();
edges.clear();
val.clear();
labels.resize(n);
edges.resize(n);
t = -1;
for(int i = 0; i < n-1; i++) edges[u[i]].pb(v[i]), edges[v[i]].pb(u[i]);
dfs(0, -1, 0);
sort(all(val), [](trio a, trio b){
if(get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
return get<1>(a) > get<1>(b);
});
for(int i = 0; i < n; i++) {
int ind = get<2>(val[i]);
labels[ind] = i;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
// primeiro descobrir se S guarda t_in ou t_out
// se S guarda t_out, então t_in[viz] < t_out[s]
// caso contrario, t_out[viz] > t_in[s]
if(sz(c) == 1) return c[0];
if(c.back() < s) {
// S guarda t_out
int t_in = c[1] - 1, t_out = s;
if(t < t_in or t_out < t) return c[0];
// caso contrário t está na sub de s
// sub[viz] = {t_in[viz], t_in[viz+1]-1}
// basta achar o primeiro cara tal que x < c[viz], a resposta é o cara anterior
auto ptr = upper_bound(all(c), t);
ptr--;
return *ptr;
}
else {
// S guarda t_in
int t_in = s, t_out = c[sz(c) - 2];
if(t < t_in or t_out < t) return c.back();
// caso contrário t está na sub de s
// sub[viz] = {t_out[viz-1]+1, t_out[viz]}
auto ptr = lower_bound(all(c), t);
return *ptr;
}
}
