#include <bits/stdc++.h>
#define MAX 1001
#define pb push_back
#include "stations.h"
#include <vector>
using namespace std;
int col[MAX],in[MAX],out[MAX],cnt=-1;
vector<vector<int>> g;
void dfs(int v,int prev){
cnt+=col[v]%2;
in[v]=cnt;
for(auto x:g[v]){
if(x==prev){
continue;
}
col[x]=1-col[v];
dfs(x,v);
}
cnt+=1-col[v]%2;
out[v]=cnt;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
g.clear();
g.resize(n);
for(int i=0;i<n-1;i++){
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
vector<int> labels(n);
col[0]=1;
dfs(0,-1);
for(int i=0;i<n;i++){
if(col[i]){
labels[i]=in[i];
}
else{
labels[i]=out[i];
}
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int tp=0;
int sz=(int)c.size();
for(auto x:c){
if(x>s){
tp=1;
}
}
if(tp==0){
for(int i=sz-1;i>0;i--){
int num=s-1;
if(i!=sz-1){
num=c[i+1]-1;
}
if(t>=c[i] && t<=num){
return c[i];
}
}
return c[0];
}
else{
for(int i=0;i<sz-1;i++){
int num=s;
if(i){
num=c[i-1];
}
if(t>=num && t<=c[i]){
return c[i];
}
}
return c[sz-1];
}
}
