#include "stations.h"
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int const NMAX = 1000;
vector <int> g[1 + NMAX];
int depth[1 + NMAX];
int ind = 0;
int in[1 + NMAX];
int out[1 + NMAX];
void DFS(int node, int parent, vector <int> &labels) {
if(depth[node] % 2 == 0) {
ind++;
labels[node-1] = ind-1;
}
for(int i = 0;i < g[node].size();i++) {
int to = g[node][i];
if(to != parent) {
depth[to] = depth[node]+1;
DFS(to, node, labels);
}
}
if(depth[node] % 2 == 1) {
ind++;
labels[node-1] = ind-1;
}
}
void normalize(vector <int> &labels) {
vector <int> aux;
for(int i = 0;i < labels.size();i++) {
aux.push_back(labels[i]);
}
sort(aux.begin(), aux.end());
aux.erase(unique(aux.begin(), aux.end()), aux.end());
map <int, int> valToPos;
for(int i = 0;i < aux.size();i++) {
valToPos[aux[i]] = i;
}
for(int i = 0;i < labels.size();i++) {
labels[i] = valToPos[labels[i]];
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
for(int i = 1;i <= n-1;i++) {
int a = u[i-1]+1, b = v[i-1]+1;
g[a].push_back(b);
g[b].push_back(a);
}
DFS(1, 1, labels);
/*
for(int i = 1;i <= n;i++) {
if(depth[i] % 2 == 0) {
labels[i-1] = in[i];
}else {
labels[i-1] = out[i];
}
}
*/
//normalize(labels);
return labels;
}
int solve1(int s, int t, vector <int> &c) {
int oldLim = s;
for(int i = 0;i < c.size()-1;i++) {
if(oldLim < t && t <= c[i]) {
return c[i];
}
oldLim = c[i];
}
return c[c.size()-1];
}
int solve2(int s, int t, vector <int> &c) {
int oldLim = s;
for(int i = c.size()-1;i > 0;i--) {
if(c[i] <= t && t < oldLim) {
return c[i];
}
oldLim = c[i];
}
return c[0];
}
int find_next_station(int s, int t, vector<int> c) {
if(s == 0) { // root / s - in / c - out
return solve1(s, t, c);
}else { //
if(s < c[0]) { // s - in / c - out
return solve1(s, t, c);
} else { // s - in / c - out
return solve2(s, t, c);
}
}
}
