#include "stations.h"

#include <bits/stdc++.h>

#include <cassert>
#include <vector>

constexpr int N = 1e3;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    std::vector<std::vector<int>> gr(n);
    for (int i = 0; i < n - 1; i++) {
        gr[u[i]].push_back(v[i]);
        gr[v[i]].push_back(u[i]);
    }
    std::vector<int> res(n);
    auto dfs = [&](auto dfs, int v, int f, int d, int& e) -> void {
        for (int t : gr[v]) {
            if (t != f) {
                dfs(dfs, t, v, d + 1, e);
            }
        }
        res[v] = e++;
    };
    int e = 0;
    for (int i = 0; i < n; i++) {
        if (gr[i].size() == 1) {
            dfs(dfs, i, -1, 0, e);
            break;
        }
    }

    return res;
}

int find_next_station(int s, int dest, std::vector<int> c) {
    assert(s != dest);
    for (int to : c) {
        if (to == dest) {
            return to;
        }
    }
    if (c.size() == 1) {
        return c.front();
    }
    for (int t : c) {
        if (s <= t && t <= dest || dest <= t && t <= s) {
            return t;
        }
    }

    assert(false);
}