#include <bits/stdc++.h>
using namespace std;
vector<int> label(int n, int _, vector<int> u, vector<int> v)
{
int cnt = 0;
vector<int> ans(n);
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, true);
return ans;
}
bool verifInter(int deb, int fin, int id)
{
return deb > fin ? deb < id or id <= fin : deb < id and id <= fin;
}
int find_next_station(int start, int target, vector<int> voisins)
{
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;
}
}
