#include <bits/stdc++.h>
#ifndef HOME
#include "stations.h"
#endif
using namespace std;
vector<int> label(int n, int _, vector<int> u, vector<int> v)
{
int cnt = 0;
vector<int> ans(n, 0);
vector<bool> vu(n, false);
vector<vector<int>> listAdj(n);
for (int i = 0; i < n; i++)
listAdj[u[i]].push_back(v[i]),
listAdj[v[i]].push_back(u[i]);
function<void(int, bool)> dfs = [&](int node, bool b)
{
if (vu[node])
return;
vu[node] = true;
if (b)
ans[node] = cnt++;
for (auto &&voisin : listAdj[node])
dfs(voisin, !b);
if (!b)
ans[node] = cnt++;
};
dfs(0, false);
return ans;
}
int find_next_station(int start, int target, std::vector<int> voisins)
{
sort(voisins.begin(), voisins.end());
if (start > voisins[0]) // current is biggest
{
if (target > start || target < voisins[0])
return voisins[0];
auto it = upper_bound(voisins.begin(), voisins.end(), target);
if (it != voisins.begin())
it--;
return *it;
}
else // current is smallest
{
if (target < start || target > voisins.back())
return voisins.back();
auto it = lower_bound(voisins.begin(), voisins.end(), target);
if (it == voisins.end())
it--;
return *it;
}
}
