#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
vector <int> g[N];
int tin[N], sz[N], h[N], tout[N];
int tmm;
void dfs(int v, int p){
tin[v] = tmm;
tmm++;
sz[v] = 1;
for(auto x : g[v]){
if(x == p) continue;
h[x] = h[v]+1;
dfs(x, v);
sz[v] += sz[x];
}
tout[v] = tmm;
tmm++;
return;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
for(int i = 0;i < n;i++){
g[i].clear();
tin[i] = sz[i] = tout[i] = h[i] = 0;
}
tmm = 0;
std::vector<int> labels;
for(int i = 0;i < n-1;i++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs(0, 0);
for(int i = 0;i < n;i++){
labels.push_back((h[i]%2 == 0 ? tin[i] : tout[i]));
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
int mn = 2010;
for(auto x : c){
mn = min(mn, x);
}
if(mn > s){
if(s == 1){
sort(c.begin(), c.end());
vector <int> c_tin = c;
int ant = s;
for(int i = 0;i < c.size();i++){
c_tin[i] = ant+1;
ant = c[i];
}
for(int i = 0;i+1 < c.size();i++){
if(c_tin[i] <= t and t <= c[i]) return c[i];
}
return c.back();
}
else{
sort(c.begin(), c.end());
vector <int> c_tin = c;
int ant = s;
for(int i = 0;i+1 < c.size();i++){
c_tin[i] = ant+1;
ant = c[i];
}
for(int i = 0;i+1 < c.size();i++){
if(c_tin[i] <= t and t <= c[i]) return c[i];
}
return c.back();
}
}
else{
sort(c.begin(), c.end());
reverse(c.begin(), c.end());
int ant = s;
vector <int> c_tout = c;
for(int i = 0;i+1 < c.size();i++){
c_tout[i] = ant-1;
ant = c[i];
}
for(int i = 0;i+1 < c.size();i++){
if(c[i] <= t and t <= c_tout[i]) return c[i];
}
return c.back();
}
}
