#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
typedef long long ll;
vector<int> link[1002];
bool visited[1002];
int arr[1002];
int sz[1002];
void szd(int x, int par=-1){
sz[x] = 1;
for(auto y: link[x]){
if(y == par) continue;
szd(y, x);
sz[x] += sz[y];
}
}
void dfs(int x, int l, int r, bool chk){
visited[x] = 1;
if(chk) arr[x] = l++;
else arr[x] = r--;
for(auto y: link[x]){
if(visited[y]) continue;
if(chk){
dfs(y, r-sz[y]+1, r, !chk);
r -= sz[y];
}
else{
dfs(y, l, l+sz[y]-1, !chk);
l += sz[y];
}
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
fill(visited, visited+n, 0);
fill(arr, arr+n, 0);
fill(sz, sz+n, 0);
for(int i=0; i<n; i++) link[i].clear();
for(int i=0; i<n-1; i++) link[u[i]].push_back(v[i]), link[v[i]].push_back(u[i]);
szd(0);
dfs(0, 0, n-1, 1);
return vector<int> (arr, arr+n);
}
int find_next_station(int s, int t, vector<int> c) {
if(s == 0){ /// 루트
sort(c.begin(), c.end());
for(auto x: c){
if(t <= x) return x;
}
exit(1);
}
else if(c[0] > s){ /// 작은 정점
sort(c.begin(), c.end());
if(t < s) return c.back();
for(auto x: c){
if(t <= x) return x;
}
exit(1);
}
else{ /// 큰 정점
sort(c.rbegin(), c.rend());
if(t > s) return c.back();
for(auto x: c){
if(t >= x) return x;
}
exit(1);
}
}
