#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
const int Nax = 1005;
class Undirected_Graph{
public:
int N, Timer = 0;
vector<vector<int>>adj;
vector<int>in;
Undirected_Graph(int _N):N(_N){
adj.resize(N);
in.resize(N);
}
inline void Add_Edge(int A, int B){
adj[A].push_back(B);
adj[B].push_back(A);
}
void Depth_First_Search(int Node, int Parent, int even = 1){
if(even)in[Node] = Timer++;
for (int& Next : adj[Node]){
if (Next == Parent)continue;
Depth_First_Search(Next,Node,even^1);
}
if (!even)in[Node] = Timer++;
}
};
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
Undirected_Graph G(n);
for (int i = 0; i < n - 1; i++){
G.Add_Edge(u[i],v[i]);
}
G.Depth_First_Search(0,0);
labels = G.in;
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if (s < c.back()){
//S is out
for (int i : c){
if (t >= i && s >= t)return i;
}
return c[0];
}else{
// S is in
for (int i : c){
if (t >= s && t <= i)return i;
}
return c.back();
}
}
