#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
vector<int>ret;
int n,timea=0,k,high[maxn];
vector<int>adj[maxn];
void dfs(int u,int par=-1){
timea++;
if(high[u]&1){
ret[u]=timea;
}
for(auto x:adj[u]){
if(x!=par){
high[x]=high[u]^1;
dfs(x,u);
}
}
timea++;
if((high[u])==0){
ret[u]=timea;
}
}
std::vector<int> label(int n_, int k_, std::vector<int> u, std::vector<int> v) {
n=n_;
k=k_;
timea=-1;
for(int i=0;i<=n;i++){
adj[i].clear();
}
for(int i=0;i<n-1;i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
high[0]=1;
ret.clear();
ret.resize(n);
dfs(0);
vector<int>allind;
for(int i=0;i<n;i++){
allind.push_back(ret[i]);
}
sort(allind.begin(),allind.end());
for(int i=0;i<n;i++){
ret[i]=lower_bound(allind.begin(),allind.end(),ret[i])-allind.begin();
}
return ret;
}
int find_next_station(int s, int t, std::vector<int> c) {
vector<int>ch;
sort(c.begin(),c.end());
int par=-1;
if((int)c.size()==1){
return c[0];
}
if(s==0){
for(int i=0;i<(int)c.size();i++){
ch.push_back(c[i]);
}
int p=lower_bound(ch.begin(),ch.end(),t)-ch.begin();
return ch[p];
}else{
if(s<c[0]){
par=c.back();
c.pop_back();
for(int i=0;i<(int)c.size();i++){
ch.push_back(c[i]);
}
if(!(t>=s&&t<=c.back())){
return par;
}
int p=lower_bound(c.begin(),c.end(),t)-c.begin();
return c[p];
}else{
par=c[0];
for(int i=1;i<(int)c.size();i++){
ch.push_back(c[i]);
}
if(!(t<=s&&t>=ch[0])){
return par;
}
int p=upper_bound(ch.begin(),ch.end(),t)-ch.begin();
return ch[p-1];
}
}
}
