#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1005];
int timeIn[1005], timeOut[1005], depth[1005], timeDfs = 0;
void dfs(int u, int pre) {
timeIn[u] = timeDfs++;
for (auto v: adj[u]) {
if (v == pre) continue;
depth[v] = depth[u] + 1;
dfs(v, u);
}
timeOut[u] = timeDfs;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
for (int i = 0; i < n; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<int> labels(n);
dfs(0, 0);
vector<int> save;
for (int i = 0; i < n; i++)
if (depth[i] % 2) labels[i] = timeOut[i];
else labels[i] = timeIn[i];
save = labels;
sort(save.begin(), save.end());
for (int i = 0; i < n; i++)
labels[i] = lower_bound(save.begin(), save.end(), labels[i]) - save.begin();
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
if (c.size() == 1) return c[0];
int ans = -1;
if (s > c.back()) {
int par = c[0];
if (t < c[1] || s <= t) return par;
int x = upper_bound(c.begin(), c.end(), t) - c.begin() - 1;
ans = c[x];
}
else {
int par = c.back();
if (s >= t || s > c[c.size() - 2]) return par;
int x = lower_bound(c.begin(), c.end(), t) - c.begin();
ans = c[x];
}
return ans;
}
