#include "stations.h"
#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
constexpr int maxn = 1010;
std::vector<int> g[maxn];
int in[maxn], out[maxn], cor[maxn], t;
void dfs(int u, int p) {
in[u] = t++;
for(int v : g[u]) if(v != p) {
cor[v] = cor[u]^1;
dfs(v, u);
}
out[u] = t++;
}
void clear() {
memset(in, 0, sizeof in);
memset(out, 0, sizeof out);
memset(cor, 0, sizeof cor);
for(int i = 0; i < maxn; i++)
g[i].clear();
t = 0;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
clear();
for(int i = 0; i < n; i++)
g[u[i]].push_back(v[i]), g[v[i]].push_back(u[i]);
dfs(0, 0);
std::map<int,int> mp;
int coord = 0;
for(int i = 0; i < n; i++)
mp[!cor[i] ? in[i] : out[i]] = 0;
for(auto& it : mp)
it.second = coord++;
std::vector<int> labels;
for(int i = 0; i < n; i++)
labels.push_back(mp[!cor[i] ? in[i] : out[i]]);
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(c[0] > s) {
// sou in, todos os meus filhos são out
if(t < s) return c.back();
for(int x : c)
if(t <= x) return x;
return c.back();
} else {
// sou out, todos os meus filhos sao in
std::reverse(c.begin(), c.end()); // comeco do meu ultimo filho
if(t > s) return c.back(); // c.back() é o meu pai
for(int x : c)
if(t >= x) return x;
return c.back();
}
}
