#include <bits/stdc++.h>
/// #include "stations.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
int timer;
vector<int> key, adj[1001];
void dfs(int v, int p, int dep) {
if(dep == 0) key[v] = timer++;
for(auto u : adj[v]) {
if(u == p) continue;
dfs(u, v, 1 - dep);
}
if(dep == 1) key[v] = timer++;
}
vector<int> label(int N, int K, vector<int> U, vector<int> V) {
timer = 0; key.assign(N, 0);
for(int l = 0; l < N; l++) adj[l].clear();
for(int l = 0; l < N - 1; l++) {
int X = U[l], Y = V[l];
adj[X].push_back(Y), adj[Y].push_back(X);
}
dfs(0, 0, 0);
return key;
}
int find_next_station(int S, int T, vector<int> C) {
if(C.size() == 1) return C[0];
bool tin = 1; int N = C.size(); T *= 2;
for(auto u : C) tin &= (u > S);
if(tin) {
int I = 2 * S, O;
if(I == 0) O = 2 * C[N - 1] + 1;
else O = 2 * C[N - 2] + 1;
if(T < I || T > O) return C[N - 1];
if(I != 0) N--;
vector<pair<int, int>> A(N);
for(int l = 1; l < N; l++) {
A[l].second = C[l] * 2;
A[l].first = C[l - 1] * 2 + 1;
}
A[0] = {S * 2 + 1, 2 * C[0]};
for(int l = 0; l < N; l++) {
I = A[l].first, O = A[l].second;
if(T > I && T < O)
return C[l];
}
return C[N];
}
else {
int I = 2 * C[1] - 1, O = 2 * S;
if(T < I || T > O) return C[0];
vector<pair<int, int>> A(N);
for(int l = 1; l < N - 1; l++) {
A[l].first = C[l] * 2;
A[l].second = C[l + 1] * 2 - 1;
}
A[N - 1] = {C[N - 1] * 2, O - 1};
for(int l = 1; l < N; l++) {
I = A[l].first, O = A[l].second;
if(T >= I && T <= O)
return C[l];
}
return C[0];
}
}
