#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1e3+10;
vector<vector<int> > graph;
int depth[MAXM];
int val[MAXM];
int seq = 0;
void dfs(int here,int p){
int there;
if(!(depth[here]&1)){
val[here] = seq;
seq++;
}
for(int i=0;i<(int)graph[here].size();i++){
there = graph[here][i];
if(there==p)continue;
depth[there] = depth[here]^1;
dfs(there,here);
}
if(depth[here]&1){
val[here] = seq;
seq++;
}
return;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
graph = vector<vector<int> > (n);
for(int i=0;i<n-1;i++){
graph[u[i]].push_back(v[i]);
graph[v[i]].push_back(u[i]);
}
dfs(0,-1);
vector<int> labels(n);
for(int i=0;i<n;i++){
labels[i] = val[i];
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
int m = (int)c.size();
if(m==1)return c[0];
int idx = -1;
int pre = 0;
int nxt = 0;
if(s<c[0]){
pre = s;
for(int i=0;i<m-1;i++){
if(pre+1<=t&&t<=c[i]){
idx = i;
break;
}
pre = c[i];
}
if(idx==-1)idx = m-1;
}
else {
for(int i=1;i<m;i++){
if(i==m-1)nxt = s;
else nxt = c[i+1];
if(c[i]<=t&&t<=nxt-1){
idx = i;
break;
}
}
if(idx==-1)idx = 0;
}
assert(idx!=-1);
return c[idx];
}
