#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);

    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 + 10;
    static std::vector<std::vector<int>> gr;
    if (gr.size() == 0) {
        gr.assign(n, {});
        for (int i = 1; i < n; i++) {
            int u = i;
            int v = i - 1 / 2 + 1;
            gr[u].push_back(v);
            gr[v].push_back(u);
        }
    }
    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, t, s)) {
            return t;
        }
    }

    assert(false);
}