#include "stations.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
namespace{
vector<vector<int>> graph;
vector<int> sz, in;
int cnt = 0;
const int inf = 1e9;
void dfs(int node, int parent){
sz[node] = 1;
int mini = inf, best = -1;
for(auto &x: graph[node]){
if(x == parent) continue;
dfs(x, node);
sz[node] += sz[x];
if(sz[x] < mini){
mini = sz[x];
best = x;
}
}
if(best != -1){
for(auto &x: graph[node]){
if(best == x){
swap(x, graph[node][(int)graph[node].size() - 1]);
break;
}
}
}
}
void dfs2(int node, int parent){
in[node] = cnt;
cnt++;
for(auto &x: graph[node]){
if(x == parent) continue;
dfs2(x, node);
}
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
sz.resize(n);
in.resize(n);
graph.resize(n);
for(int i = 0; i < n - 1; i++){
graph[u[i]].push_back(v[i]);
graph[v[i]].push_back(u[i]);
}
dfs(0, 0);
dfs2(0, 0);
vector<int> ret(n);
for(int i = 0; i < n; i++){
ret[i] = sz[i] * 1000 + in[i];
}
return ret;
}
int find_next_station(int s, int t, std::vector<int> c){
int lab = t % 1000;
int up = 0;
for(auto &x: c){
int sz = x / 1000, in = x % 1000;
if(in < s % 1000){
up = x;
continue;
}
int out = in + sz - 1;
if(in <= lab && lab <= out) return x;
}
return up;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g stations.cpp stub.cpp
