#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
vector<int> label(int N, int K, vector<int> u, vector<int> v)
{
vector<vector<int>> con(N);
for (int i=0;i<N-1;i++)
con[u[i]].push_back(v[i]),
con[v[i]].push_back(u[i]);
vector<int> labels(N);
function<void(int, int)> dfs;
dfs = [&](int n, int p){
static int idx = 0;
if (p == -1 || !labels[p]) labels[n] = ++idx;
for (int t: con[n]) if (t != p)
dfs(t, n);
if (labels[p]) labels[n] = ++idx;
};
dfs(0, -1);
return labels;
}
int find_next_station(int s, int t, vector<int> c)
{
if (c.back() < s) reverse(c.begin(), c.end());
for (int x: c) if (min(s, x) <= t && t <= max(s, x)) return x;
return c.back();
}
