#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int timer;
int tin[N], tout[N];
vector <vector<int>> g;
void dfs(int v, int p) {
tin[v] = ++timer;
for (auto it : g[v]) {
if (it == p) continue;
dfs(it, v);
}
tout[v] = timer;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
timer = -1;
g.clear();
g.resize(n);
for (int i = 0; i < n - 1; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs(0, 0);
vector <int> ans(n);
for (int i = 0; i < n; i++) {
ans[i] = tin[i] * 1000 + tout[i];
}
return ans;
}
int contains(int x, int y) {
if (x / 1000 <= y / 1000 && x % 1000 >= y % 1000) return true;
return false;
}
int find_next_station(int s, int t, vector<int> c) {
if (contains(s, t)) {
for (auto it : c) {
if (contains(it, t) && contains(s, it)) return it;
}
}
else {
for (auto it : c) {
if (!contains(s, it)) return it;
}
}
assert(false);
}
