#include "stations.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct TR{
struct no{
vector<int> ch;
int lb=-1;
};
vector<no> v;
void init(int x){
v.resize(x);
}
void add(int x,int y){
v[x].ch.push_back(y);
v[y].ch.push_back(x);
}
int cnt=0;
void dfs(int r,int f,int d){
if(d%2==0){
v[r].lb=cnt;
cnt++;
}
for(auto h:v[r].ch){
if(h!=f){
dfs(h,r,d+1);
}
}
if(d%2){
v[r].lb=cnt;
cnt++;
}
}
};
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
TR tr;
tr.init(n);
for(int i=0;i<n-1;i++){
tr.add(u[i],v[i]);
}
tr.dfs(0,0,0);
vector<int> labels(n);
for (int i = 0; i < n; i++) {
labels[i] = tr.v[i].lb;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
for(auto h:c){
if(h==t){
return h;
}
}
if(c.size()==1){
return c[0];
}
sort(c.begin(),c.end());
if(s<c[0]){
for(auto h:c){
if(t>=s && t<=h){
return h;
}
}
return c.back();
}
else{
reverse(c.begin(),c.end());
for(auto h:c){
if(t<=s && t>=h){
return h;
}
}
return c.back();
}
}
