#include<bits/stdc++.h>
#include "stations.h"
using namespace std;
const int N=5005;
struct edge{
	int to,nxt;
}e[N<<1];
int hd[N],ct,dt,dfn[N],d[N];
inline void add(int u,int v){
	e[++ct]=(edge){v,hd[u]};hd[u]=ct;
	e[++ct]=(edge){u,hd[v]};hd[v]=ct;
}
void ch(int u,int fa){
	d[u]=d[fa]+1;
	if(d[u]&1) dfn[u]=++dt;
	for(int i=hd[u],v;i;i=e[i].nxt){
		v=e[i].to;
		if(v==fa) continue;
		ch(v,u);
	}
	if(!(d[u]&1)) dfn[u]=++dt; 
}
vector<int> label(int n,int k,vector<int> U,vector<int> V){
	vector<int> labels(n);
	ct=dt=0;memset(hd,0,(n+1)<<2);
	for(int i=0;i<n-1;i++) add(U[i],V[i]);
	ch(0,0);
	for(int i=0;i<n;i++) labels[i]=dfn[i]-1;
	return labels;
}
inline int max(vector<int> c){
	return *max_element(c.begin(),c.end());
}
inline int min(vector<int> c){
	return *min_element(c.begin(),c.end());
}
int find_next_station(int s,int t,vector<int> c){
	if(s>max(c)){
		int mi=s?min(c):-1;
		vector<int> o;
		for(int u:c) if(u!=mi) o.push_back(u);
		if(t>s||t<min(o)) return mi;
		sort(o.begin(),o.end());
		return *prev(upper_bound(o.begin(),o.end(),t));
	}
	else{
		int mx=s?max(c):1e9;
		vector<int> o;
		for(int u:c) if(u!=mx) o.push_back(u);
		if(t<s||t>max(o)) return mx;
		sort(o.begin(),o.end());
		return *lower_bound(o.begin(),o.end(),t);
	}
}