#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
int ind=0;
void dfs(int v, int p, int h, vector<vector<int> >& adi, vector<int>& lab){
if(h%2==0){
lab[v]=ind;
}
ind++;
for(auto u: adi[v]){
if(u==p) continue;
dfs(u, v, h+1, adi, lab);
}
if(h%2==1){
lab[v]=ind;
}
ind++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<vector<int> > adi(n);
for(int i=0; i<n-1; i++){
adi[v[i]].push_back(u[i]);
adi[u[i]].push_back(v[i]);
}
ind=0;
vector<int> lab(n, -1);
dfs(0, -1, 0, adi, lab);
return lab;
}
int find_next_station(int s, int t, vector<int> c) {
int p=c[0];
vector<int> children;
for(int i=1; i<(int)c.size(); i++){
children.push_back(c[i]);
}
if(s==0){
p=-1;
children = c;
}
if(children.empty()){
return p;
}
int pres=s;
int posts=s;
if(c[0]<s){
pres = children[0]-1;
}
else{
posts = children.back()+1;
}
if(t<pres || posts<t){
return p;
}
int next=-1;
if(c[0] < s){
next=children[0];
for(auto e: children){
if(e<=t){
next=e;
}
}
}
else{
next=children.back();
for(int i=children.size(); i>=0; i--){
if(t<=children[i]){
next=children[i];
}
}
}
return next;
}
