#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
const int MAXN = 1e3 + 10;
int pre[MAXN], pos[MAXN], color[MAXN];
vector<int> adj[MAXN];
int t = 0;
void dfs(int v, int p){
pre[v] = ++t;
for(auto u : adj[v]){
if(u != p){
color[u] = 1 - color[v];
dfs(u, v);
}
}
pos[v] = t;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
t = 0;
for(int i=0; i<n; i++) adj[i].clear();
vector<int> labels(n);
for(int i=0; i<(n - 1); i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
color[0] = 0;
dfs(0, 0);
for(int i=0; i<n; i++){
if(color[i]){
labels[i] = pre[i];
} else labels[i] = pos[i] + n;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c){
sort(c.begin(), c.end());
if(s < c[0]){
// s eh pre e todo o resto eh pos
int pre_s = s, pos_s = s;
if((int) c.size() > 1) pos_s = c[(int) c.size() - 2];
if(pre_s <= t && t <= pos_s){
int pos = lower_bound(c.begin(), c.end(), t) - c.begin();
return c[pos];
}
return c.back();
}
// s eh pos e todo o resto eh pre
int pre_s = s, pos_s = s;
if((int) c.size() > 2) pre_s = c[1] - 1;
if(pre_s <= t && t <= pos_s){
int pos = upper_bound(c.begin(), c.end(), t) - c.begin();
if(pos == 0) return -1;
return c[pos - 1];
}
return c[0];
}
