#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
const int MAXN = 1e3 + 10;
int pre[MAXN], pos[MAXN];
vector<int> adj[MAXN];
int t = 0;
void dfs(int v, int p){
pre[v] = ++t;
for(auto u : adj[v]){
if(u != p){
dfs(u, v);
}
}
pos[v] = t;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
t = 0;
for(int i=0; i<n; i++) adj[i].clear();
vector<int> labels(n);
for(int i=0; i<(n - 1); i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, 0);
for(int i=0; i<n; i++) labels[i] = pre[i] + (pos[i] << 10);
return labels;
}
int find_pai(int v, int pre_v, int pos_v, vector<int> &c){
for(auto u : c){
int pre_u = u % (1 << 10), pos_u = u - pre_u;
if(pre_u <= pre_v && pos_v <= pos_u) return u;
}
return 0;
}
int find_next_station(int s, int t, vector<int> c){
// alguns casos
int pre_s = s % (1 << 10), pos_s = s - pre_s;
int pre_t = t % (1 << 10), pos_t = t - pre_t;
int pai = find_pai(s, pre_s, pos_s, c);
// se t contido em s
if(pre_s <= pre_t && pos_t <= pos_s){
// acha o filho que contem t
for(auto x : c){
if(x == pai) continue;
int cur_pre = x % (1 << 10), cur_pos = x - cur_pre;
if(cur_pre <= pre_t && pos_t <= cur_pos) return x;
}
}
return pai;
}
