#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
void dfs(vector<vector<int>> &connections, int node, int depth, int &count, vector<int> &cons){
if (cons[node]!=-1)return;
++depth;
if (depth%2!=0){++count;cons[node]=count;}
else cons[node]=-2;
for (int it : connections[node]){
dfs(connections,it,depth,count,cons);
}
if (depth%2==0){++count;cons[node]=count;}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<vector<int>> connections(n);
for (int i = 0; i < n-1; i++) {
connections[u[i]].push_back(v[i]);
connections[v[i]].push_back(u[i]);
}
vector<int> cons(n,-1);
int count = -1;
dfs(connections,0,-1,count,cons);
return cons;
}
int find_next_station(int s, int t, std::vector<int> c) {
int csize=c.size();
if (s<c[0]){
int bf = s;
for (int i = 0; i < csize-1;++i){
if (t > bf && t<=c[i])return c[i];
bf=c[i];
}
return c[csize-1];
}else{
reverse(c.begin(),c.end());
int bf = s;
for (int i = 0; i < csize-1;++i){
if (t >=c[i] && t<bf)return c[i];
bf=c[i];
}
return c[csize-1];
}
}
