#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
void dfs(int x, int p, vector < vector < int > > &adj, vector < int > &labels, int depth) {
static int timer = -1;
++timer;
if(depth) labels[x] = timer;
for(int to : adj[x]) {
if(to != p) {
dfs(to, x, adj, labels, depth ^ 1);
}
}
++timer;
if(!depth) labels[x] = timer;
}
vector < int > label(int n, int k, vector < int > u, vector < int > v) {
vector < int > labels(n);
vector< vector < int > > adj(n, vector < int >());
for(int i = 0; i < n - 1; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, -1, adj, labels, 0);
vector < vector < int > > g;
for(int i = 0; i < n; ++i) {
g.push_back({labels[i], i});
}
sort(g.begin(), g.end());
for(int i = 0; i < n; ++i) {
labels[g[i][1]] = i;
}
return labels;
}
int find_next_station(int s, int t, vector < int > c) {
if(c.size() == 1) return c[0];
sort(c.begin(), c.end());
if(s == 0) {
int my_in = 0;
int my_out = c.back();
for(int i = 0; i < c.size(); ++i) {
int cur_in, cur_out;
if(i == 0) {
cur_in = my_in;
} else {
cur_in = c[i - 1] + 1;
}
cur_out = c[i];
if(cur_in <= t && t <= cur_out) {
return c[i];
}
}
} else {
int my_in = -1, my_out = -1;
if(s < c[0]) {
my_in = s;
my_out = c[(int)c.size() - 2];
for(int i = 0; i < (int)c.size() - 1; ++i) {
int cur_in, cur_out;
cur_out = c[i];
if(i == 0) {
cur_in = my_in;
} else {
cur_in = c[i - 1] + 1;
}
if(cur_in <= t && t <= cur_out) return c[i];
}
return c.back();
} else {
my_in = c[1];
my_out = s;
for(int i = 1; i < (int)c.size(); ++i) {
int cur_in, cur_out;
cur_in = c[i];
if(i == (int)c.size() - 1) {
cur_out = s;
} else {
cur_out = c[i + 1] - 1;
}
if(cur_in <= t && t <= cur_out) return c[i];
}
return c[0];
}
}
}
// int main() {
// vector < int > x = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
// // for(int i : x) cout << i << ' ';
// cout << find_next_station(3, 9, {5}) << '\n';
// }
