#include "stations.h"
#include <vector>
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e3 + 7;
vector<int> tin,tout,lv;
void dfs(vector<vector<int>> g, int x, int p, int &G)
{
tin[x] = G++;
for(auto y : g[x]){
if(y == p)continue;
lv[y] = 1 - lv[x];
dfs(g, y, x, G);
}
tout[x] = G++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
vector<vector<int>> g(n + 7);
tin.resize(n + 7);
tout.resize(n + 7);
lv.resize(n + 7);
for(int i = 0; i < n - 1; i++){
int x = u[i], y = v[i];
g[x].push_back(y);
g[y].push_back(x);
}
int st = 0;
dfs(g, 0, 0, st);
vector<int> op;
for(int i = 0; i < n; i++){
if(lv[i])labels[i] = tin[i];
else labels[i] = tout[i];
op.push_back(labels[i]);
}
sort(op.begin(), op.end());
st = 0;
vector<int> used(3 * n + 7, 0);
for(auto x : op){
used[x] = st++;
}
for(int i = 0; i < n; i++){
labels[i] = used[labels[i]];
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(s < c[0]){
vector<pair<int, int>> nc;
int ls = s;
for(int i = 0; i + 1 < (int)c.size(); i++){
nc.push_back({ls, c[i]});
ls = c[i] + 1;
}
for(auto x : nc){
if(x.fi <= t && t <= x.se){
return x.se;
}
}
return c.back();
}else{
assert(s > c.back());
vector<pair<int, int>> nc;
int ls = s - 1;
for(int i = (int)c.size() - 1; i > 0; i--){
nc.push_back({c[i], ls});
ls = c[i] - 1;
}
for(auto x : nc){
if(x.fi <= t && t <= x.se){
return x.fi;
}
}
return c[0];
}
}
