#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

typedef int ll;

vector<ll> dfs(ll v, ll p, vector<vector<ll>>& arr) {
	vector<ll> ans(1, v);
	for (auto i : arr[v]) {
		if (i != p) {
			vector<ll> now = dfs(i, v, arr);
			reverse(now.begin(), now.end());
			for (auto j : now) {
				ans.push_back(j);
			}
		}
	}
	return ans;
}

vector<ll> label(ll n, ll k, vector<ll> u, vector<ll> v) {
	vector<vector<ll>> arr(n);
	for (ll i = 0; i < n - 1; i++) {
		arr[u[i]].push_back(v[i]);
		arr[v[i]].push_back(u[i]);
	}
	vector<ll> per = dfs(0, 0, arr);
	vector<ll> num(n);
	for (ll i = 0; i < n; i++) {
		num[per[i]] = i;
	}
	return num;
}

ll find_next_station(ll s, ll t, vector<ll> c) {
	if (c[0] > s) {
		sort(c.begin(), c.end());
		if (t < s) {
			return c.back();
		}
		for (ll i = 0; i < c.size(); i++) {
			if (t <= c[i]) {
				return c[i];
			}
		}
		return c.back();
	} else {
		sort(c.rbegin(), c.rend());
		if (t > s) {
			return c.back();
		}
		for (ll i = 0; i < c.size(); i++) {
			if (t >= c[i]) {
				return c[i];
			}
		}
		return c.back();
	}
}