#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
int compteur = 0;
vector<vector<int>> graphe;
vector<int> labels;
void dfs(int noeud, int profondeur) {
if (profondeur%2 == 0) {
labels[noeud] = compteur;
compteur++;
}
else {
labels[noeud] = compteur;
}
for (int iVoisin : graphe[noeud]) {
if (labels[iVoisin] == -1) dfs(iVoisin, profondeur+1);
}
if (profondeur%2 == 1) {
labels[noeud] = compteur;
compteur++;
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
labels.assign(n, -1);
graphe.assign(n, {});
for (int i = 0; i < n-1; i++) {
graphe[u[i]].push_back(v[i]);
graphe[v[i]].push_back(u[i]);
}
dfs(0, 0);
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
c.push_back(s);
int in, out;
if (c[0] > s) {
sort(c.rbegin(), c.rend());
in = s;
out = c[1];
}
else {
sort(c.begin(), c.end());
in = c[1];
out = s;
}
if (t < in || t > out) {
return c[0];
}
int idx = 0;
while (idx < c.size() && t > c[idx]) idx++;
if (c[0] > s) {
return c[idx];
}
return c[idx-1];
}
