#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> tmp, adj[1005];
int num;
void dfs(int cur, int prev, bool mx) {
if(!mx) tmp[cur] = num++;
for(int next:adj[cur]) {
if(next==prev) continue;
dfs(next, cur, !mx);
}
if(mx) tmp[cur] = num++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
tmp.resize(n);
num = 0;
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]);
}
dfs(0, -1, 0);
for(int i=0;i<n;i++) labels[i] = tmp[i];
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
int it = 0;
if(s<c[0]) {
if(t<s) it = c.size()-1;
else it = lower_bound(c.begin(), c.end(), t)-c.begin();
} else {
if(t>s) it = 0;
else it = upper_bound(c.begin(), c.end(), t)-c.begin()-1;
}
return c[it];
}
