#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> v1[1010];
int dp[1010];
int ans[1010];
int l[1010];
int r1[1010];
vector<int> labels1;
void f(int u,int pa){
for(auto g:v1[u]){
if(g!=pa){
f(g,u);
dp[u]+=dp[g];
}
}
dp[u]+=1;
return;
}
void lab(int u,int lv,int pa){
int ll=l[u];
int rr=r1[u];
if(lv%2==1){
ans[u]=ll;
ll+=1;
}
else{
ans[u]=rr;
}
for(int g:v1[u]){
if(g!=pa){
l[g]=ll;
ll+=dp[g];
r1[g]=ll-1;
lab(g,lv+1,u);
}
}
return;
}
vector<int> label(int n, int k, std::vector<int> x, std::vector<int> y) {
for(int i=0;i<n-1;i++){
v1[x[i]].push_back(y[i]);
v1[y[i]].push_back(x[i]);
}
f(0,-1);
l[0]=0;
r1[0]=n-1;
lab(0,1,-1);
for(int i=0;i<n;i++){
labels1.push_back(ans[i]);
}
return labels1;
}
int find_next_station(int s, int t, std::vector<int> c) {
int mini=c[0];
int maxi=c[0];
for(auto g:c){
mini=min(mini,g);
maxi=max(maxi,g);
}
int xx;
if(s>c[0]){
xx=mini;
for(auto g:c){
if(g<=t){
xx=max(xx,g);
}
}
if(t>s)
xx=mini;
}
if(s<c[0]){
xx=maxi;
for(auto g:c){
if(g>=t){
xx=min(xx,g);
}
}
if(t<s)
xx=maxi;
}
return xx;
}
