#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
int val;
const int N = 1005;
vector <int> labels;
vector <vector <int> > paths(N);
void traversal(int pos, int par, int order) {
if (order) labels[pos] = val++;
for (auto el : paths[pos]) {
if (el == par) continue;
traversal(el, pos, (order^1));
}
if (!order) labels[pos] = val++;
}
vector <int> label(int n, int k, vector <int> u, vector <int> v) {
val = 0;
labels.resize(n);
for (int i = 0; i < n; i++) paths[i].clear();
for (int i = 0; i < n - 1; i++) {
int a = u[i], b = v[i];
paths[a].push_back(b);
paths[b].push_back(a);
}
traversal(0, 0, 0);
// for (int i = 0; i < n; i++) cout << i << ": " << labels[i] << '\n';
return labels;
}
int find_next_station(int a, int b, vector <int> adj) {
int st, end, sz = adj.size(), ans;
if (sz == 1) return adj[0];
for (auto el : adj) if (el == b) return b;
if (adj[0] > a) {
st = a;
end = adj[sz-2];
if (st <= b && b <= end) {
ans = *lower_bound(adj.begin(), adj.end(), b);
} else {
ans = adj[sz-1];
}
} else {
end = a;
st = adj[1];
if (st <= b && b <= end) {
ans = *(--lower_bound(adj.begin(), adj.end(), b));
} else {
ans = adj[0];
}
}
return ans;
}
