#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
int t=0;
int tin[maxn];
int tout[maxn];
int res[maxn];
vector<int> g[maxn];
void dfs(int node,int d=0,int par=-1){
tin[node]=t++;
for(int i:g[node]){
if(i==par) continue;
dfs(i,d+1,node);
}
tout[node]=t++;
if(d&1) res[node]=tin[node];
else res[node]=tout[node];
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
for(int i=0;i<n;i++) g[i].clear();
for(int i=0;i<n-1;i++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs(0);
for(int i=0;i<n;i++) labels[i]=res[i];
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int maxi=*max_element(c.begin(),c.end());
vector<pair<int,int> > decoo(int(c.size())-1);
if(maxi>s){ // on je in
int cale=c.back();
c.pop_back();
for(int i=0;i<int(c.size());i++) decoo[i].second=c[i];
int prosli=s;
for(int i=0;i<int(c.size());i++){
decoo[i].first=prosli+1;
prosli=decoo[i].second;
}
for(int i=0;i<int(c.size());i++){
if(decoo[i].first<=t && t<=decoo[i].second) return decoo[i].second;
}
return cale;
}else{ //on je out
int cale=c.front();
c.erase(c.begin());
for(int i=0;i<int(c.size());i++) decoo[i].first=c[i];
int prosli=s;
for(int i=int(c.size())-1;i>=0;i--){
decoo[i].second=prosli-1;
prosli=decoo[i].first;
}
for(int i=0;i<int(c.size());i++){
if(decoo[i].first<=t && t<=decoo[i].second) return decoo[i].first;
}
return cale;
}
return c[0];
}
