#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int v, vector<vector<int>> &g, vector<int> &pre, vector<int> &post, int &T, vector<int>&odw) {
T++;
pre[v] = T;
for (int u : g[v]) {
if (!odw[u]) {
odw[u] = odw[v]^3;
dfs(u, g, pre, post, T, odw);
}
}
T++;
post[v] = T;
}
vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
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]);
}
vector<int> pre (n, 0), post (n, 0);
vector<int> odw (n, 0);
int T = 0;
odw[0] = 1;
dfs(0, g, pre, post, T, odw);
vector<pair<int, int>> t;
for (int i = 0; i < n; i++) {
if (odw[i] == 1) {
t.push_back({pre[i], i});
}
else {
t.push_back({post[i], i});
}
}
sort(t.begin(), t.end());
vector<int> labels (n, 0);
for (int i = 0; i < n; i++) {
labels[t[i].second] = i;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
sort(c.begin(), c.end());
for (int i : c) {
if (t == i) {
return i;
}
}
if (s < c[0]) {
if (t <= s) {
return c[c.size()-1];
}
for (int i : c) {
if (t <= i) {
return i;
}
}
return c[c.size()-1];
}
if (t >= s) {
return c[0];
}
for (int i = c.size()-1; i >= 0; i--) {
if (c[i] <= t) {
return c[i];
}
}
return c[0];
}
