#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
bool line = 1;
bool binary = 1;
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 < n-1; i++) {
if (u[i] > v[i]) swap(u[i], v[i]);
binary &= (v[i] + 1) / 2 == (u[i] + 1);
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int r = -1;
for (int i = 0; i < n; i++) {
if (adj[i].size() == 1) r = i;
line &= adj[i].size() <= 2;
}
if (line) {
vector<int> ans(n);
int t = 0;
auto dfs = [&](auto&& s, int v, int p) -> void {
ans[v] = t++;
for (int u : adj[v]) if (u != p) s(s, u, v);
};
dfs(dfs, r, -1);
return ans;
}
if (binary) {
vector<int> ans(n);
iota(ans.begin(), ans.end(), 0);
return ans;
}
return {};
}
int find_next_station(int s, int t, std::vector<int> c) {
if (line) {
for (int x : c) if ((x-s)*(x-t) <= 0) return x;
}
if (binary) {
int ls = 31 - __builtin_clz(s+1), lt = 31 - __builtin_clz(t+1);
if (ls > lt) {
for (int x : c) if (x < s) return x;
assert(0);
}
else {
for (int x : c) if (x > s) {
bool F = 0;
for (int tmp = t+1; tmp; tmp /= 2) {
if (tmp == x+1) {
F = 1;
break;
}
}
if (F) return x;
}
for (int x : c) if (x < s) return x;
assert(0);
}
}
assert(0);
}
