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

using namespace std;

constexpr int X = 999;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    std::vector<int> labels(n);
    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]);
    }
    if (k > 1000) {
        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 * X;
        };
        dfs(dfs, 0, -1);
        labels[0] = 0;
        return labels;
    } else {
        int bin = 1;
        for (int i = 0; i + 1 < n; ++i) {
            if (min(u[i], v[i]) == i / 2 && max(u[i], v[i]) == i + 1) {
                bin = true;
            } else {
                bin = false;
                break;
            }
        }
        if (bin) {
            iota(labels.begin(), labels.end(), 0);
            return labels;
        }
        int leaf = 0;
        while (adj[leaf].size() == 2) {
            leaf += 1;
        }
        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);
                }
            }
        };
        dfs(dfs, leaf, -1);
        return labels;
    }
}

pair<int, int> decode(int x) {
    if (x == 0) {
        return {0, 1e9};
    } else {
        int tin = x % X;
        if (tin == 0) {
            tin = X;
        }
        return {tin, (x - tin) / X};
    }
}

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) {
    for (int to : c) {
        if (to == t) {
            return to;
        }
    }
    if (max({s, t, *max_element(c.begin(), c.end())}) > 1000) {
        auto [tins, touts] = decode(s);
        auto [tint, toutt] = decode(t);
        if (isp(tins, touts, tint, toutt)) {
            for (int to: c) {
                auto [into, outo] = decode(to);
                if (!isp(into, outo, tins, touts) && isp(into, outo, tint, toutt)) {
                    return to;
                }
            }
        } else {
            for (int to: c) {
                auto [into, outo] = decode(to);
                if (isp(into, outo, tins, touts)) {
                    return to;
                }
            }
        }
        assert(false);
        return -1;
    } else {
        int bin = 1;
        for (int to : c) {
            int mx = max(to, s);
            int mn = min(to, s);
            if ((mx - 1) / 2 != mn) {
                bin = false;
            }
        }
        if (!bin) {
            for (int to : c) {
                if ((to < s) == (t < s)) {
                    return to;
                }
            }
            assert(false);
        }
        int x = t;
        while (x > s && !binary_search(c.begin(), c.end(), x)) {
            x /= 2;
        }
        if (x <= s) {
            for (int to : c) {
                if (to < s) {
                    return to;
                }
            }
        }
        return x;
    }
}