#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std ;
vector <int> adj[1003] ;
int L[1003],R[1003] ;
int cnt=0 ;
void dfs(int x,int par){
L[x]=cnt++ ;
R[x]=L[x] ;
for (auto a : adj[x]){
if (a!=par){
dfs(a,x) ;
R[x]=R[a] ;
}
}
}
std::vector<int> label(int N, int K, std::vector<int> u, std::vector<int> v) {
int i,j ;
for (i = 0 ; i < N ; i ++) adj[i].clear() ;
cnt=0 ;
for (i = 0 ; i < N-1 ; i ++){
adj[u[i]].push_back(v[i]) ;
adj[v[i]].push_back(u[i]) ;
}
dfs(0,-1) ;
vector <int> vv ;
for (i = 0 ; i < N ; i ++){
vv.push_back(1000*L[i]+R[i]) ;
}
return vv;
}
int find_next_station(int s, int t, std::vector<int> c) {
int a1,b1,a2,b2 ;
a1=s/1000 ;
b1=s%1000 ;
a2=t/1000 ;
b2=t%1000 ;
int i,j ;
int par ;
for (auto a : c){
int a3=a/1000 ;
int b3=a%1000 ;
if (a3<=a2&&b2<=b3&&!(a3<=a1&&b1<=b3)) return a ;
if (a3<=a1&&b1<=b3) par=a ;
}
return par ;
}
