#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;
int parent = -1;
for(int x : c){
int x_ = x/1001;
int sub = x % 1001;
if(x_ <= s_ && s_ < x_ + sub){
parent = x;
}
}
for(int x : c){
int x_ = x/1001;
int sub = x % 1001;
if(x_ <= t_ && t_ < x_ + sub){
return x;
}
}
return parent;
}
