#include "stations.h"
#include <vector>
const int MAXN = 1000 + 10;
std::vector<std::vector<int>> adj;
std::vector<int> labels;
int counter = 0;
void dfs(int u, int parent, int parity)
{
if (parity == 0)
labels[u] = counter++;
for (int v : adj[u])
if (v != parent)
dfs(v, u, parity ^ 1);
if (parity == 1)
labels[u] = counter++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v)
{
adj = std::vector<std::vector<int>>(n);
labels = std::vector<int>(n, 0);
counter = 0;
for (int i = 0; i < n - 1; ++i)
{
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, -1, 0);
return labels;
}
int find_next_station(int s, int t, std::vector<int> c)
{
if (c.size() == 1)
return c[0];
if (s < c[0])
{
if (s > t || c[c.size() - 1 - 1] < t)
return c.back();
for (int i = 0; i < c.size() - 1; ++i)
{
if (c[i] >= t)
return c[i];
}
}
else if (s > c[0])
{
if (s < t || c[1] > t)
return c.front();
c.push_back(1e9+1);
for (int i = 1; i < c.size(); ++i)
if (c[i] > t)
return c[i - 1];
}
return c[0]; // ! impossible case - satisying compiler warning :D
}
