#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, out;
Undirected_Graph(int _N):N(_N){
adj.resize(N);
out.resize(N);
in.resize(N);
}
inline void Add_Edge(int A, int B){
adj[A].push_back(B);
adj[B].push_back(A);
}
inline void Depth_First_Search(int Node, int Parent){
in[Node] = Timer++;
for (int& Next : adj[Node]){
if (Next == Parent)continue;
Depth_First_Search(Next,Node);
}
out[Node] = Timer - 1;
}
};
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);
for (int i = 0; i < n; i++){
labels[i] = 1000 * G.in[i] + G.out[i];
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
int index = 0, n = (int)c.size();
for (int i = 0; i < n; i++){
int in = c[i] / 1000;
int out = c[i] % 100;
if (in <= s/1000 && out >= s%1000){
index = i;
//parent
continue;
}
if (t / 1000 >= in && t / 1000 <= out){
return c[i];
}
}
return c[index];
}
