#include "stations.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));
const int mod = 1e9 + 7;
const matrix II = {{1, 0}, {0, 1}};
const int N = 1e3 + 5;
const int LG = 10;
int n;
vector <int> adj[N];
int par[N][LG];
vector <int> labell(N), revlabel(N), depth(N);
int idx = 0;
void dfs(int u, int p){
par[u][0] = p;
depth[u] = depth[p] + 1;
if (depth[u] % 2) labell[u] = idx++;
for (auto v : adj[u]) {
if (v == p) continue;
dfs(v, u);
}
if (depth[u] % 2 == 0) labell[u] = idx++;
}
std::vector<int> label(int nn, int k, std::vector<int> u, std::vector<int> v) {
n = nn;
idx = 0;
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < n - 1; i++) {
adj[u[i]].emb(v[i]);
adj[v[i]].emb(u[i]);
}
memset(par, -1, sizeof par);
labell.resize(n);
dfs(0, 0);
for (int i = 0; i < n; i++) revlabel[labell[i]] = i;
return labell;
}
int find_next_station(int s, int t, std::vector<int> c) {
sort(all(c)); int sz = c.size();
if (s < c[0]) { // in
if (t >= s && t <= c[0]) return c[0];
for (int i = 0; i + 1 < sz - 1; i++) {
if (t >= c[i] + 1 && t <= c[i + 1]) return c[i + 1];
}
return c.back();
}
else { // out
if (t >= c.back() && t <= s) return c.back();
for (int i = 1; i + 1 < sz; i++) {
if (t >= c[i] && t <= c[i + 1] - 1) return c[i];
}
return c[0];
}
}
