#include "stations.h"
#include <vector>
#include <algorithm>
#define vec vector
#define For(i, n) for(int i = 0; i < n; i++)
using namespace std;
void dfs(int x, vec<int>&odp, vec<vec<int>>&g, int &et, int typ, int pr = -1){
if(typ == 1) { odp[x] = et; et++; }
for(auto &i : g[x]){
if(i == pr) continue;
dfs(i, odp, g, et, 1 - typ, x);
}
if(typ == 0) { odp[x] = et; et++; }
return;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
vec<int> odp(n);
vec<vec<int>> g(n);
For(i, u.size()){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
int et = 0;
dfs(0, odp, g, et, 0);
return odp;
}
int find_next_station(int s, int t, std::vector<int> c) {
vec<int> p;
if(c[0] > s){
int maxi = s;
if(c.size() >= 2) maxi = c[c.size()-2];
if(t < s || t > maxi) return c.back();
int qq = lower_bound(c.begin(), c.end(), t) - c.begin();
return c[qq];
}
else{
int mini = s;
if(c.size() >= 2) mini = c[1];
if(t < mini || t > s) return c[0];
c.push_back(s);
int qq = upper_bound(c.begin(), c.end(), t) - c.begin() - 1;
return c[qq];
}
return -1;
}
