#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
#define FOR(i, s, e) for (int i = s; i < e; i++)
using namespace std;
const int MAX = 1000;
std::vector<int> label(int N, int K, std::vector<int> U, std::vector<int> V) {
vector<vector<int>> graph(N);
FOR(i, 0, N-1) graph[U[i]].push_back(V[i]), graph[V[i]].push_back(U[i]);
int t = 0;
vector<int> tin(N, -1), sz(N);
function<void(int)> dfs = [&](int cur) {
tin[cur] = t++;
sz[cur] = 1;
for (int nxt: graph[cur]) {
if (tin[nxt] != -1) continue;
dfs(nxt);
sz[cur] += sz[nxt];
}
}; dfs(0);
vector<int> label(N);
FOR(i, 0, N) label[i] = tin[i]*MAX+(sz[i]-1) +1;
return label;
}
int find_next_station(int s, int t, std::vector<int> c) {
s--, t--;
int ssz = s%MAX+1, stin = s/MAX;
int tsz = t%MAX+1, ttin = t/MAX;
int p = -1, a = -1;
for (int n: c) {
n--;
int nsz = n%MAX+1, ntin = n/MAX;
if (nsz > ssz) p = n;
else if (ntin <= ttin && ttin < ntin+nsz) a = n;
}
if (a != -1) return a+1;
return p+1;
}
