// In the name of Allah
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2000 + 4;
int n, k;
vector<int> adj[maxn];
int h[maxn], timer;
vector<int> A;
void dfs(int v, int p = -1) {
if (h[v] % 2 == 0) A[v] = timer++;
for (int u : adj[v]) {
if (u == p) continue;
h[u] = h[v] + 1;
dfs(u, v);
}
if (h[v] % 2 == 1) A[v] = timer++;
}
vector<int> label(int Nx, int Kx, vector<int> ux, vector<int> vx) {
n = Nx; k = Kx;
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < n - 1; i++) {
int u = ux[i], v = vx[i];
adj[u].pb(v); adj[v].pb(u);
}
A.clear(); A.resize(n);
timer = 0; dfs(0);
return A;
}
int find_next_station(int s, int t, vector<int> ls) {
if (len(ls) == 1) return ls[0];
sort(all(ls));
if (ls[0] > s) {
int p = ls.back(); ls.pop_back();
int l = s + 1;
for (int r : ls) {
if (t >= l && t <= r) return r;
l = r + 1;
}
return p;
}
else {
reverse(all(ls));
int p = ls.back(); ls.pop_back();
int r = s - 1;
for (int l : ls) {
if (t >= l && t <= r) return l;
r = l - 1;
}
return p;
}
}
