#include "stations.h"
#include "bits/stdc++.h"
#define st first
#define nd second
using namespace std;
void dfs(int x, int p, vector<int>& h, vector<vector<int>>& g, vector<int>& path) {
h[x] = h[p] + 1;
path.push_back(x);
for(int i: g[x]) {
if(i != p) {
dfs(i, x, h, g, path);
}
}
path.push_back(x);
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
vector<vector<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]);
}
for(int i=0; i<n; ++i) {
sort(g[i].begin(), g[i].end());
}
vector<int> h(n), path;
dfs(0, 0, h, g, path);
vector<vector<int>> pos(n);
for(int i=0; i<(int)path.size(); ++i) {
pos[path[i]].push_back(i);
}
vector<pair<int, int>> val(n);
for(int i=0; i<n; ++i) {
val[i].nd = i;
if(h[i]%2==1) {
val[i].st = pos[i][1];
}
else {
val[i].st = pos[i][0];
}
}
sort(val.begin(), val.end());
for(int i=0; i<n; ++i) {
labels[val[i].nd] = i;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int sz = c.size();
sort(c.begin(), c.end());
if(c.size()==1) return c[0];
for(int i: c) if(t==i) return i;
if(c.back() > s) { // s is pre
int prv = s;
for(int i=0; i<sz-1; ++i) {
if(t > prv && t < c[i]) {
return c[i];
}
prv = c[i];
}
return c.back();
}
else { // s is post
int prv = s;
for(int i=sz-1; i>=1; --i) {
if(t < prv && t > c[i]) {
return c[i];
}
prv = c[i];
}
return c[0];
}
}
