#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;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
vector<int> labels(n,-1);
vector<int> coor;
vector<vector<int>> adj(n);
for(int i{};i < n-1;i++){
adj[u[i]].emplace_back(v[i]);
adj[v[i]].emplace_back(u[i]);
}
int t = 0;
auto dfs = [&](int pos,int h,int p,auto&& self)->void{
int intime = t++;
for(auto k:adj[pos]){
if(k == p) continue;
self(k,h+1,pos,self);
}
int outtime = t++;
int val = intime;
if(h&1) val = outtime;
labels[pos] = val;
coor.emplace_back(val);
//cout << pos << " " << val << endl;
};
dfs(0,0,-1,dfs);
sort(all(coor));
for(int i{};i < n;i++){
labels[i] = lower_bound(all(coor),labels[i])-coor.begin();
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
//cout << "Query : " << s << " to " << t << ":" << endl;
int maxi = s;
int mini = s;
for(auto k:c) maxi = max(maxi,k),mini = min(mini,k);//,cout << k << " ";
//cout << endl;
if(mini <= t && maxi >= t){
if(maxi == s){
return *(upper_bound(all(c),t)-1);
}
else{
return *lower_bound(all(c),t);
}
}
else{
if(maxi == s) return mini;
else return maxi;
}
return c[0];
// if(s < t){
// if(t > c.back()) return c.back();
// else return *(upper_bound(all(c),t)-1);
// }
// else return c.front();
}
