#include "stations.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
vector<vector<int>> adj(n);
for(int i=0;i<n-1;i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<int> st(n),en(n);
vector<int> d(n);
int timer=-1;
function<void(int,int)> dfs=[&](int v,int p){
st[v]=++timer;
for(auto u:adj[v]){
if(u==p) continue;
d[u]=d[v]+1;
dfs(u,v);
}
en[v]=timer;
};
dfs(0,-1);
vector<pair<pair<int,int>,pair<int,int>>> ord;
for(int i=0;i<n;i++){
if(d[i]%2==0) ord.push_back({{st[i],0},{-d[i],i}});
else ord.push_back({{en[i],0},{-d[i],i}});
}
sort(all(ord));
vector<int> label(n);
for(int i=0;i<n;i++){
label[ord[i].s.s]=i;
}
return label;
}
int find_next_station(int S, int T, std::vector<int> C) {
vector<int> c=C;
bool even=true;
for(auto v:c){
if(v<S) even=false;
}
int l,r;
if(even){
l=S;
sort(all(c));
if((int)c.size()==1) r=l;
else r=c[(int)c.size()-2];
}
else{
r=S;
sort(all(c));
if((int)c.size()==1) l=r;
else l=c[1];
}
if(l<=T and T<=r){
if(even){
for(auto v:c){
if(T<=v) return v;
}
}
else{
reverse(all(c));
for(auto v:c){
if(v<=T) return v;
}
}
}
else{
for(auto v:c){
if(v<l or r<v) return v;
}
}
assert(false);
}
