#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > adj;
vector<int> subtree;
vector<int> order;
int idx = 0;
void dfs(int u, int p){
subtree[u] = 1;
order[idx++] = u;
for(int v : adj[u]){
if(v != p){
dfs(v, u);
subtree[u] += subtree[v];
}
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
adj.resize(n);
subtree.resize(n);
order.resize(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, -1);
vector<int> val(n);
for(int i = 0; i < n; i++){
val[order[i]] = 1001 * i + subtree[order[i]];
}
for(int i = 0; i < n; i++){
adj[i].clear();
subtree[i] = 0;
order[i] = 0;
}
order.clear();
subtree.clear();
adj.clear();
idx = 0;
return val;
}
int find_next_station(int s, int t, vector<int> c){
int s_ = s/1001;
int t_ = t/1001;
if(s_ > t_){
return c[0];
}
else{
int lst = -1;
for(int x : c){
int thing = x/1001;
int subtreeSX = x % 1001;
if(thing <= t_ && t_ < thing + subtreeSX){
lst = x;
}
}
return lst;
}
}
