#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define pb push_back
vector<vi> g;
vi ans, sz, d, used;
int cur = 0;
void dfs1(int u = 0, int p = -1){
for (int v : g[u]){
if (v == p) continue;
d[v] = d[u] + 1;
dfs1(v, u);
sz[u] += sz[v] + 1;
}
}
void dfs2(int u = 0, int p = -1){
if (d[u] % 2 == 0){
used[cur] = 1;
ans[u] = cur;
while (used[cur]) cur++;
}else{
used[cur+sz[u]] = 1;
ans[u] = cur+sz[u];
while (used[cur]) cur++;
}
for (int v : g[u]){
if (v == p) continue;
dfs2(v, u);
}
}
vi label(int n, int k, vi u, vi v) {
g.resize(n);
ans.resize(n); used.resize(n);
d.resize(n); sz.resize(n);
for (int i = 0; i < n-1; i++){
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
dfs1();
dfs2();
return ans;
}
int find_next_station(int s, int t, vi c) {
int C = c.size();
if (C==1) return c[0];
if (s < c[0]){
if (t < s || t >= c[C-1]) return c[C-1];
int pos = C-1;
for (int i = C-2; i >= 0; i--){
if (t < c[i+1] && t >= c[i]){
pos = i; break;
}
}
return c[pos];
}
if (t > s || t <= c[0]) return c[0];
int pos = 0;
for (int i = 1; i < C; i++){
if (t > c[i-1] && t <= c[i]){
pos = i; break;
}
}
return c[pos];
}
