#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 &time) {
ta[i] = time++;
for (int j : ej[i])
if (j != p)
dfs(ej, ta, tb, i, j, time);
tb[i] = time - 1;
}
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, time);
for (i = 0; i < n; i++)
labels[i] = ta[i] * N + tb[i];
return labels;
}
int find_next_station(int s, int t, vi cc) {
int m = cc.size(), h;
for (h = 0; h < m; h++)
if (cc[h] / N > s / N && cc[h] / N <= t / N && t / N <= cc[h] % N)
return cc[h];
for (h = 0; h < m; h++)
if (cc[h] / N < s / N)
return cc[h];
return -1;
}
