#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    vector<vector<int>> adj(n);
    for (int i = 0; i + 1 < n; ++i) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
	std::vector<int> labels(n);
    int T = 0;
    auto dfs = [&](auto self, int v, int par) -> void {
        labels[v] += T++;
        for (int to : adj[v]) {
            if (to != par) {
                self(self, to, v);
            }
        }
        labels[v] += T * 1000;
    };
    dfs(dfs, 0, -1);
	return labels;
}

bool isp(int a, int b, int c, int d) {
    return a <= c && b >= d;
}

int find_next_station(int s, int t, std::vector<int> c) {
    int tins = s % 1000, touts = s / 1000, tint = t % 1000, toutt = t / 1000;
    if (isp(tins, touts, tint, toutt)) {
        for (int to : c) {
            if (!isp(to % 1000, to / 1000, tins, touts) && isp(to % 1000, to / 1000, tint, toutt)) {
                return to;
            }
        }
    } else {
        for (int to : c) {
            if (isp(to % 1000, to / 1000, tins, touts)) {
                return to;
            }
        }
    }
    assert(false);
	return -1;
}