#include <iostream>
#include "stations.h"
#include <vector>
bool debug=0;
using namespace std;
#define pb push_back
#define mp make_pair
vector<vector<int>> adj;
vector<int> bl; // base labels (euler search)
int cur=0;
void dfs(int node){ // used to initialise `bl`
bl[node] = cur;
cur++;
for(int e:adj[node]){
if(bl[e]==-1){
dfs(e);
}
}
return;
}
vector<int> ml; // max-labels (max bl of all children)
int get_ml(int node){
if(ml[node]!=-1)return ml[node];
int answer=bl[node];
for(int e:adj[node]){
if(bl[e]>bl[node]){ // is that a child?
answer=max(answer, get_ml(e));
}
}
return ml[node] = answer;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
bl = vector<int>(n, -1);
ml = vector<int>(n, -1);
adj = vector<vector<int>>(n);
for(int i=0; i<n-1; i++){
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
}
dfs(0);
get_ml(0);
vector<int> labels(n);
for(int i=0; i<n; i++){
labels[i] = 1000*bl[i] + ml[i];
}
if(debug)
{
cout<<"$ LABELS ARE AS FOLLOWS:\n";
for(int i=0; i<n; i++){
cout<<labels[i]<<"\n";
}
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
for(int i=0; i<c.size(); i++){
if(c[i] == t){
return c[i];
}
}
int bgoal = t/1000;
int min=s/1000,max=s%1000;
int base,tmax;
if(bgoal<min || bgoal>max){
// we have to travel up (towards the root)
for(int i=0; i<c.size(); i++){
base = c[i]/1000;
if(base < min){
// this is the way up
return c[i];
}
}
} else{
// we have to travel down the tree
for(int i=0; i<c.size(); i++){
base = c[i]/1000;
tmax = c[i]%1000;
if(base <= bgoal && tmax >= max){
return c[i];
}
}
}
return -1;
}
