#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+5;
int sub[MAXN];
vector <int> ans;
vector <int> adj[MAXN];
void fil(int cur,int par,int L,int R,bool B) {
if (B) {
ans[cur] = L;
for (int nxt : adj[cur]) {
if (nxt == par) continue;
fil(nxt,cur,R-sub[nxt]+1,R,!B);
R -= sub[nxt];
}
}
else {
ans[cur] = R;
for (int nxt : adj[cur]) {
if (nxt == par) continue;
fil(nxt,cur,L,L+sub[nxt]-1,!B);
L += sub[nxt];
}
}
}
void calc(int cur,int par) {
sub[cur] = 1;
for (int nxt : adj[cur]) {
if (nxt == par) continue;
calc(nxt,cur);
sub[cur] += sub[nxt];
}
}
vector<int> label(int N,int K,vector<int> u,vector<int> v) {
for (int i=0;i<N;i++) {
adj[i].clear();
}
ans = vector<int>(N);
for (int i=0;i<N-1;i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
calc(0,0);
fil(0,0,0,N-1,0);
return ans;
}
int find_next_station(int s,int t,vector<int> c) {
if (s > c[0]) {
reverse(c.begin(),c.end());
for (int x : c) {
if (t < s && t >= x) {
return x;
}
}
}
else {
for (int x : c) {
if (t > s && t <= x) {
return x;
}
}
}
return c.back();
}
