#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAX_N=1010;
vector<vi> G;
int in[MAX_N],out[MAX_N];
int it;
void dfs(int u,int p){
in[u]=out[u]=it; it++;
for(auto &v:G[u]){
if(v!=p){
dfs(v,u);
out[u]=max(out[v],out[u]);
}
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
G.clear(); G.resize(n+1);
memset(in,0,sizeof in); memset(out,0,sizeof out);
it=0;
for(int i=0;i<n-1;i++){
G[u[i]].push_back(v[i]);
G[v[i]].push_back(u[i]);
}
dfs(0,-1);
vector<int> lab;
for(int i=0;i<n;i++){
lab.push_back(out[i]*10000+in[i]);
}
return lab;
}
int find_next_station(int s, int t, std::vector<int> c) {
int pa=-1,hj=-1;
int lt,rt;
lt=t%10000;
rt=t/10000;
int ls,rs;
ls=s%10000;
rs=s/10000;
for(auto &v:c){
int l,r;
l=v%10000;
r=v/10000;
if(l<=ls && rs<=r){
pa=v;
continue;
}
if(l<=lt && rt<=r) hj=v;
}
//cout<<s<<" "<<t<<" "<<hj<<" "<<pa<<endl;
if(hj==-1) return pa;
return hj;
}
