#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include "stations.h"
using namespace std;
vector<vector<int>> adj;
vector<int> lb;
vector<int> indx;
int t = 0;
void dfs(int st){
if(indx[st] != -1) return;
indx[st] = t;
lb[st] = t*1000;
t++;
for(auto i : adj[st]) dfs(i);
lb[st] += t-1;
}
vector<int> label (int n, int k, vector<int> u, vector<int> v){
t = 0;
adj.assign(n, {});
for(int i = 0; i<n-1; i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
lb.assign(n, -1);
indx.assign(n, -1);
dfs(0);
return lb;
}
int subtree(int par, int u){
return (((par/1000) <= (u/1000)) && ((u%1000) <= (par%1000)));
}
int find_next_station(int s, int t, vector<int> c){
int par = 0;
for(auto i : c){
if(subtree(i, t) && !subtree(i, s)) return i;
else if(subtree(i, s)) par = i;
}
return par;
}
// int main(void){
// freopen("input.txt", "r", stdin);
// int n; cin>>n;
// vector<int> u(n-1, 0);
// vector<int> v(n-1, 0);
// for(int i = 0; i<n-1; i++) cin>>u[i]>>v[i];
// label(n, 100000000, u, v);
// // cout<<find_next_station(3, 6);
// }
