#include "stations.h"
#include <vector>
#include <queue>
#include <stack>
#include <iostream>
#include <algorithm>
#define endl '\n'
#define all(x) begin(x),end(x)
using namespace std;
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
vector<int> labels(n, -1);
vector<vector<int>> adj(n);
vector<bool> vis(n);
for(int i{};i < n-1;i++){
adj[u[i]].emplace_back(v[i]);
adj[v[i]].emplace_back(u[i]);
}
stack<int> q;
q.emplace(0);
vis[0] = 1;
int t = 0;
while(!q.empty()){
auto hd = q.top();q.pop();
labels[hd] = t++;
for(auto k:adj[hd]){
if(!vis[k]){
q.emplace(k);
vis[k] = 1;
}
}
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
// cout << "Query : " << s << " to " << t << ":" << endl;
// for(auto k:c) cout << k << " ";
// cout << endl;
if(s < t){
if(t > c.back()) return c.back();
else return *(upper_bound(all(c),t)-1);
}
else return c.front();
}
