#include "bits/stdc++.h"
#include "stations.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 10005;
vector<int> v[N];
int tin[N],tout[N],col[N],ti=0;
void dfs(int c,int p,int d){
tin[c]=++ti;
for(int x:v[c]){
if(x==p) continue;
dfs(x,c,d^1);
tout[c]=max(tout[c],tout[x]);
}
tout[c]=++ti;
if(d) col[c]=tin[c];
else col[c]=tout[c];
}
vector<int> label(int n, int k, vector<int> u, vector<int> g){
vector<int> labels(n);
for(int i=0;i<n-1;i++){
int a=u[i],b=g[i];
v[a].push_back(b);
v[b].push_back(a);
}
dfs(0,0,0);
for(int i=0;i<n;i++) labels[i]=col[i];
return labels;
}
int find_next_station(int s, int t, vector<int> c){
sort(all(c));
int n=sz(c);
if(n==1) return c[0];
if(s<c[0]){
int out=c[n-2];
if(!(t>=s && t<=out)) return c[n-1];
int in=s+1;
for(int i=0;i<n-1;i++){
if(t>=in && t<=c[i]) return c[i];
in=c[i]+1;
}
return c[n-1];
}
int in=c[1]-1;
if(!(t>=in && t<=s)) return c[0];
int out=s;
for(int i=n-1;i>0;i--){
if(t>=c[i] && t<=out) return c[i];
out=c[i]-1;
}
return 2323232323;
}
