#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1010;
vector<int>graph[MAXN], ord, aux(MAXN), sub_size(MAXN), inv(MAXN), labels;
void dfs(int x, int p){
ord.push_back(x);
aux[x]=0;
for(int k=0;k<graph[x].size();k++){
int neighbour=graph[x][k];
if(neighbour!=p){
dfs(neighbour, x);
aux[x]+=1+aux[neighbour];
}
}
}
vector<int> label(int n, int m, vector<int>a, vector<int>b){
for(int k=0;k<n;k++){
graph[k].clear();
}
ord.clear();
for(int k=0;k<n-1;k++){
graph[a[k]].push_back(b[k]);
graph[b[k]].push_back(a[k]);
}
dfs(0, 0);
labels.resize(n);
for(int k=0;k<n;k++){
labels[ord[k]]=k;
inv[k]=ord[k];
sub_size[k]=aux[ord[k]];
}
for(int k=0;k<n;k++){
for(int i=0;i<graph[k].size();i++){
graph[k][i]=labels[graph[k][i]];
}
sort(graph[k].begin(), graph[k].end());
}
return labels;
}
int find_next_station(int at, int end, vector<int>adj){
if(end>at+sub_size[at] or end<at){
return graph[inv[at]][0];
}
for(int k=graph[inv[at]].size()-1;k>0;k--){
if(end>=graph[inv[at]][k]){
return graph[inv[at]][k];
}
}
return 0;
}
/*int main(){
int r;
cin>>r;
while(r--){
int n, m;
cin>>n>>m;
vector<int>a(n-1), b(n-1);
for(int k=0;k<n-1;k++){
cin>>a[k];
}
for(int k=0;k<n-1;k++){
cin>>b[k];
}
label(n, m, a, b);
int q;
cin>>q;
int at, end;
for(int k=0;k<q;k++){
cin>>at>>end;
vector<int>adj;
for(int i=0;i<graph[at].size();i++){
adj.push_back(graph[at][i]);
}
sort(adj.begin(), adj.end());
cout<<find_next_station(at, end, adj)<<endl<<endl;
}
}
}*/
