#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
matrix<int> g(n);
for(int i = 0; i < n-1; i++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
int timer = -1;
vector<int> labels(n);
auto dfs =[&](int id, int last, int height, auto dfs)->void{
if(!height)
labels[id] = ++timer;
for(int i : g[id]){
if(i!=last)
dfs(i,id,height^1,dfs);
}
if(height)
labels[id] = ++timer;
};
dfs(0,0,0,dfs);
return labels;
}
bool intersect(int l, int r, int v){
if(r < l)
swap(l,r);
return l <= v && v <= r;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(c[0] < s)
reverse(all(c));
int ini = 0, fim = int(c.size())-1;
while(ini!=fim){
int m = (ini+fim)>>1;
if(intersect(s,c[m],t))
fim = m;
else ini = m+1;
}
return c[ini];
}
