#include<bits/stdc++.h>
// #include"stations.h"
// #define DEBUG
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define sz(a) ((int) (a).size())
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define vi vector<int>
#define ull unsigned long long
using namespace std;
const int N = 1 << 21, mod = 1e9 + 7;
vi label(int n, int k, vi u, vi v) {
	vi deg(n);
	L(i, 0, n - 2) deg[u[i]] += 1, deg[v[i]] += 1;
	int root = 0;
	L(i, 0, n - 1) if(deg[i] == 1) root = i;
	vi fa(n, -1);
	vector<vi>e(n);
	vi dep(n);
	L(i, 0, n - 2)e[u[i]].pb(v[i]),e[v[i]].pb(u[i]);
	vi dfn(n), en(n);
	int idt = 0;
	function<void(int)>dfs=[&](int x) ->void {
		dfn[x]=++idt;
		for(auto&v:e[x])if(v!=fa[x]){
			fa[v]=x,dep[v]=dep[x]+1,dfs(v);
		}
		en[x]=idt;
	};
	dfs(0);
	vector<vi>ls(n+1),rs(n+1);
	L(i, 0, n - 1){
		if(dep[i] & 1) {
			// cout<<i<<" use"<<dfn[i]<<endl;
			ls[dfn[i]].pb(i);
		} else {
			// cout<<i<<" use "<<en[i]<<endl;
			rs[en[i]].pb(i);
		}
	}
	int top = 0;
	vi ans(n);
	L(i, 0, n) {
		sort(ls[i].begin(), ls[i].end(), [&] (int x, int y) {
			return dep[x] < dep[y];
		});
		sort(rs[i].begin(), rs[i].end(), [&] (int x, int y) {
			return dep[x] > dep[y];
		});
		for(auto&u : ls[i]) 
			ans[u] = ++top;
		for(auto&u : rs[i]) 
			ans[u] = ++top;
	}
	return ans;
}
int find_next_station(int s, int t, vi c) {
	if(sz(c) == 1) return c[0];
	sort(c.begin(), c.end());
	if(c[0] < s) {
		if(c[1] <= t && t <= s) {
			R(i, sz(c) - 1, 0) {
				if(c[i] <= t) {
					return c[i];
				}
			}
		} 
		return c[0];
	} else {
		if(s <= t && t <= c[sz(c) - 2]) {
			L(i, 0, sz(c) - 1) {
				if(t <= c[i]) {
					return c[i];
				}
			}
		} 
		return c[sz(c) - 2];
	}
}
// int main() {
// 	ios :: sync_with_stdio(false);
// 	cin.tie(0); cout.tie(0);
// 	auto lab = label(5, 10, vi{0, 1, 1, 2}, vi{1, 2, 3, 4});
// 	for(auto u : lab)cout << u << ' ';
// 	cout << endl;
// 	cout << "nxt_1 = " << find_next_station(1, 2, vi{3, 4, 5}) << endl;
// 	return 0;
// }