#include "stations.h"
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 1000;
void dfs(vector<vi> ej, vi &ta, vi &tb, int p, int i, int d, int &time) {
if (d % 2 == 0)
ta[i] = time++;
for (int j : ej[i])
if (j != p)
dfs(ej, ta, tb, i, j, d + 1, time);
if (d % 2 == 1)
ta[i] = time++;
}
vi label(int n, int k, vi uu, vi vv) {
vector<vi> ej(n);
vi ta(n, 0), tb(n, 0), labels(n, 0);
int h, i, time;
for (h = 0; h < n - 1; h++) {
ej[uu[h]].push_back(vv[h]);
ej[vv[h]].push_back(uu[h]);
}
time = 0, dfs(ej, ta, tb, -1, 0, 0, time);
for (i = 0; i < n; i++)
labels[i] = ta[i];
return labels;
}
int find_next_station(int s, int t, vi cc) {
int m = cc.size(), h;
if (s < cc[0]) {
for (h = 0; h < m - 1; h++)
if ((h == 0 ? s : cc[h - 1]) < t && t <= cc[h])
break;
} else {
for (h = m - 1; h > 0; h--)
if ((h + 1 == m ? s : cc[h + 1]) > t && t >= cc[h])
break;
}
return cc[h];
}
