#include "stations.h"
#include <bits/stdc++.h>
int lab=0;
std::vector<int> adj[1010];
std::vector<int> Labels;
void dfs(int curr,int par,bool b){
if(b)Labels[curr]=lab++;
for(auto to:adj[curr]){
if(to==par)continue;
dfs(to,curr,!b);
}
if(!b)Labels[curr]=lab++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
Labels.resize(n);
for(int i=0;i<n-1;i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0,0,0);
//for(auto num:Labels)std::cout << num << ' ';
return Labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
//std::sort(c.begin(),c.end());
bool mi=false;
for(auto num:c){
if(num>s)
mi=true;
if(num==t)return num;
}
if(mi){
if(t>c.back()||t<s)return c[c.size()-1];
int idx = std::upper_bound(c.begin(),c.end(),t)-c.begin();
return c[std::min(idx,(int)(c.size()-1))];
}
else{
if(t<=*c.begin()||t>s)return c[0];
int idx = std::lower_bound(c.begin(),c.end(),t)-c.begin();
return c[std::min(idx,(int)(c.size()-1))];
}
}
