#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++;
    };
    for (int i = 0; i < n; i++) {
        res[i] = i;
    }

    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();
    // }

    int n = N;
    std::vector<std::vector<int>> gr(n);
    for (int i = 1; i < n; i++) {
        gr[i / 2].push_back(i + 1);
        gr[i + 1].push_back(i / 2);
    }
    auto dfs = [&](auto dfs, int v, int f) -> bool {
        if (v == dest) {
            return true;
        }
        for (int t : gr[v]) {
            if (t != f) {
                if (dfs(dfs, t, v)) {
                    return true;
                }
            }
        }
        return false;
    };
    for (int t : c) {
        if (dfs(dfs, s, t)) {
            return t;
        }
    }

    assert(false);
}