#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) {
rank[node] = ind;
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) {
rank[node] = ind;
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-1;i++) {
int a = u[i];
int b = v[i];
g[a].push_back(b);
g[b].push_back(a);
}
DFS(0);
for(int i = 0;i < n;i++) {
labels[i] = rank[i];
}
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
sort(c.begin(), c.end());
//std::cerr << "\"" << s << ' ' << t;
//for(int i = 0;i < c.size();i++) {
// std::cerr << ' ' << c[i];
//}
//std::cerr << "\"\n";
if(s < c[0]) { // s = in => c = out
if(s == 0) { // root, no parent
for(int i = 0;i < c.size();i++) {
if(c[i]+1 <= t && t <= c[i+1]) {// v[i+1].in = v[i].out+1 c[i] holds out
return c[i+1];
}
}
return c[0]; // c[0] remaining child
}else {
// parent is biggest in the c = out case -> c[c.size()-1] = parent
for(int i = 0;i+1 < c.size();i++) {
if(c[i]+1 <= t && t <= c[i+1]) {
return c[i+1];
}
}
if(s+1 <= t && t <= c[0]) { // v[0].in = s.in+1
return c[0];
}
return c[c.size()-1];
}
} else { // s = out => c = in -> also no root case
// parent in 0
for(int i = 1;i < c.size();i++) {
if(c[i] <= t && t <= c[i+1]-1) { // c[i].out = c[i+1].in-1
return c[i];
}
}
if(c[c.size()-1] <= t && t <= s-1) { //
return c[c.size()-1];
}
return c[0];
}
}
