#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define pb push_back
vi labels(1005);
#define sz(u) (int(u.size()))
int dfs(int no, int fat, int time, vvi &ed){
int label = time;
time++;
int subtreesz = 1;
for(auto e:ed[no]){
if(e == fat)continue;
subtreesz += dfs(e, no, time, ed);
}
label *= 1000;
label += subtreesz;
labels[no] = label;
return subtreesz;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
vvi ed(n+1);
for(int i = 0; i < sz(u); ++i){
ed[u[i]].pb(v[i]);
ed[v[i]].pb(u[i]);
}
dfs(0, -1, 0, ed);
vi ans;
for(int i = 0; i < n; ++i){
ans.pb(labels[i]);
}
return ans;
}
int find_next_station(int s, int t, std::vector<int> c) {
int source = s / 1000;
int target = t / 1000;
int ssize = s % 1000;
if( (target < source) || (target > (source + (ssize) - 1) ) ){
for(auto e:c){
int node = e/1000;
if(node < source){
return e;
}
}
return c[0];
}else{
for(auto e:c){
int node = e / 1000;
int nodesize = e % 1000;
if(target >= node && target <= (node + nodesize - 1)){
return e;
}
}
return c[0];
}
}
