#include "stations.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
typedef long long llong;
const int MAXN = 1000 + 10;
int n;
int timer;
int in[MAXN];
int out[MAXN];
bool which[MAXN];
std::vector <int> g[MAXN];
void dfs(int node, int p)
{
in[node] = timer++;
for (const int &i : g[node])
{
if (i == p) continue;
which[i] = 1 ^ which[node];
dfs(i, node);
}
out[node] = timer++;
}
std::vector <int> label(int _n, int k, std::vector <int> u, std::vector <int> v)
{
n = _n;
std::fill(which, which + n, 0);
for (int i = 0 ; i < n ; ++i)
{
g[i].clear();
}
for (int i = 0 ; i < n - 1 ; ++i)
{
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
timer = 0;
dfs(0, -1);
std::vector <int> labels(n);
std::vector <std::pair <int,int>> compr;
for (int i = 0 ; i < n ; ++i)
{
labels[i] = (which[i] ? in[i] : out[i]);
compr.push_back({labels[i], i});
}
std::sort(compr.begin(), compr.end());
for (int i = 0 ; i < n ; ++i)
{
labels[compr[i].second] = i;
}
return labels;
}
int find_next_station(int s, int t, std::vector <int> c)
{
std::sort(c.begin(), c.end());
if (s < c[0]) // in time
{
if (t < s)
{
return c.back();
}
for (int i = 0 ; i < (int)(c.size() - 1) ; ++i)
{
if (c[i] >= t)
{
return c[i];
}
}
return c.back();
} else
{
if (t > s)
{
return c[0];
}
for (int i = (int)c.size() - 1 ; i > 0 ; --i)
{
if (c[i] <= t)
{
return c[i];
}
}
return c[0];
}
std::cout << "WTF\n";
}
