#include <bits/stdc++.h>
#include "stations.h"
#include <vector>
using namespace std;
int d[1005];
int in[1005];
int out[1005];
int t;
vector <vector<int>> g(1005);
void dfs(int x, int p) {
in[x] = t++;
for (auto to:g[x]) {
if (to == p) continue;
d[to] = d[x] + 1;
dfs(to,x);
}
out[x] = t;
}
vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
for (int i = 0; i < n; i++) g[i].clear();
for (int i =0; i < n-1; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
t = 0;
d[0] = 0;
dfs(0,0);
for (int i =0; i < n; i++) {
if (d[i]%2) {
labels[i] = in[i];
} else {
labels[i] = out[i];
}
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
int mn = INT_MAX;
int mx = -INT_MAX;
int n = c.size();
for (int i = 0; i < n; i++) {
mn = min(mn,c[i]);
mx = max(mx,c[i]);
}
if (s <= mn) {
for (int i = 0; i < n-1; i++) {
int in = s+1;
int out = c[i];
if (in <= t && t <= out) {
return c[i];
}
}
return c[n-1];
}
for (int i = 1; i < n; i++) {
int in = c[i];
int out = s;
if (i != n-1) out = c[i+1]-1;
if (in <= t && t <= out) {
return c[i];
}
}
return c[0];
}
