#include "stations.h"
#include <vector>
#include <iostream>
#include <algorithm>
int const NMAX = 1000;
std::vector <int> g[1 + NMAX];
int depth[1 + NMAX];
bool visit[1 + NMAX];
int ind;
int rank[1 + NMAX];
void DFS(int node) {
visit[node] = true;
if(depth[node] % 2 == 0) {
ind++;
rank[node] = ind;
}
for(int i = 0;i < g[node].size();i++) {
int to = g[node][i];
if(visit[to] == false) {
depth[to] = depth[node] + 1;
DFS(to);
}
}
if(depth[node] % 2 == 1) {
ind++;
rank[node] = ind;
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels;
labels.resize(n);
for (int i = 0; i < n; i++) {
labels[i] = i;
}
for(int i = 0;i < n-1;i++) {
int a = u[i];
int b = v[i];
g[a].push_back(b);
g[b].push_back(a);
}
DFS(1);
for(int i = 0;i < n;i++) {
labels[i] = rank[i];
}
//std::cerr << '\n';
for(int i = 0;i < n;i++) {
//std::cerr << " " << labels[i] << ' ';
}
//std::cerr << '\n';
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
// find if s is in or out label "in" if smallest, "out" if biggest
return 0;
sort(c.begin(), c.end());
if(s < c[0]) { // s = in
if(s == 0) { // root, no parent
for(int i = 1;i < c.size();i++) {
if(c[i-1] <= t && t <= c[i]-1) { // out c i-1 = (in c i) - 1
return c[i-1];
}
}
return c[c.size()-1];
}else {
// c[0] is parent,
for(int i = 2;i < c.size();i++) {
if(c[i-1] <= t && t <= c[i]-1) { // out c i-1 = (in c i) - 1
return c[i-1];
}
}
// c[c.size()-1] out = s out - 1
if(c[c.size()-1] <= t && t <= s-1) {
return c[c.size()-1];
}
// if not anything, but parent
return c[0];
}
} else { // s = out
// no root
// parent is in c.size()-1
for(int i = 1;i < c.size()-1;i++) {
if(c[i-1] + 1 <= t && t <= c[i]) { // sorted based on outs, in c[i] = out c[i-1] + 1
return c[i];
}
}
// in or i = 0 is in s + 1
if(s + 1 <= t && t <= c[0]) {
return c[0];
}
return c[c.size()-1];
}
}
