#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n, sz[maxn] = {0}, h[maxn], x[maxn] = {0}; // even = mn, odd = mx
vector<int> adj[maxn];
void dfs1(int v, int p, int height){
h[v] = height; sz[v] = 1;
for (auto u : adj[v]){
if (u == p) continue;
dfs1(u, v, height + 1);
sz[v] += sz[u];
}
}
void dfs2(int v, int p, int l, int r){
if (h[v] % 2) x[v] = r--; // mx
else x[v] = l++; // mn
for (auto u : adj[v]){
if (u == p) continue;
dfs2(u, v, l, l + sz[u] - 1);
l += sz[u];
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
for (int i = 0; i < n - 1; i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
// for (int i = 0; i < n; i++){
// cout << i << ": ";
// for (auto u : adj[i]) cout << u << ' ';
// cout << endl;
// }
dfs1(0, 0, 0);
dfs2(0, 0, 0, n - 1);
vector<int> re(n);
for (int i = 0; i < n; i++) re[i] = x[i];
// for (int i = 0; i < n; i++) cout << x[i] << ' '; cout << endl;
// for (int i = 0; i < n; i++) cout << h[i] << ' '; cout << endl;
return re;
}
int find_next_station(int s, int t, vector<int> c){
if (c.size() == 1) return c.front();
if (s < c[0]){ // x[s] is min, root
if (t < s || t > c.back()){ // not its children, go up
return c.back();
}
else{ // else, go down, looking for smallest element in c >= t
int idx = lower_bound(c.begin(), c.end(), t) - c.begin();
return c[idx];
}
}
else{ // x[s] is max
if (t > s || t < c[1]) return c.front();
else{
int idx = upper_bound(c.begin(), c.end(), t) - c.begin();
return c[idx - 1];
}
}
}
