#include "stations.h"
#include <vector>
const int P = 1000;
std::vector<std::vector<int>> G;
std::vector<int> labels;
int timeDfs;
void DFS(int node = 0) {
labels[node] = (timeDfs++) * P;
for (int v : G[node])
if (labels[v] == -1)
DFS(v);
labels[node] += timeDfs;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
G.assign(n, std::vector<int>());
labels.assign(n, 0);
timeDfs = 0 ;
for (int i = 0; i < n - 1; i++) {
G[u[i]].push_back(v[i]);
G[v[i]].push_back(u[i]);
}
DFS();
return labels;
}
inline bool inside(int a, int b) {
return a / P <= b / P && b % P <= a % P;
}
int find_next_station(int s, int t, std::vector<int> c) {
int parent = -1;
for (int node : c)
if (inside(node, s))
parent = node;
for (int node : c)
if (node != parent && inside(node, t))
return node;
return parent;
}
