#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
//#define int long long
using namespace std;
const int N = 1001, INDEFINI = -1;
const pii TOUT = {-1, 1e6};
int deb[N], fin[N];
int profondeur[N];
int temps = 0;
bool vu[N];
vector<int> voisins[N];
void dfs(int noeud, int etage){
vu[noeud] = true;
deb[noeud] = (temps++)/2;
profondeur[noeud] = etage;
for (int voisin : voisins[noeud]){
if (vu[voisin]) continue;
dfs(voisin, etage + 1);
}
fin[noeud] = (temps++)/2;
}
vector<int> label(int nNoeuds, int labelMax, vector<int> u, vector<int> v) {
temps = 0;
for (int noeud = 0; noeud < nNoeuds; ++noeud){
deb[noeud] = fin[noeud] = INDEFINI;
vu[noeud] = false;
voisins[noeud] = {};
}
for (int i = 0; i < nNoeuds - 1; ++i){
voisins[u[i]].pb(v[i]);
voisins[v[i]].pb(u[i]);
}
dfs(0, 0);
vector<int> labels(nNoeuds);
for (int i = 0; i < nNoeuds; ++i){
if (profondeur[i]%2 == 0)
labels[i] = deb[i];
else
labels[i] = fin[i];
}
return labels;
}
int find_next_station(int source, int dest, vector<int> voisins) {
if (sz(voisins) == 1)
return voisins[0];
vector<pii> inters;
if (voisins[0] < source){
//on est une fin
inters.pb(TOUT);
for (int i = 1; i < sz(voisins) - 1; ++i)
inters.pb({voisins[i], voisins[i + 1] - 1});
inters.pb({voisins.back(), source - 1});
}
else {
//on est un debut
inters.pb({source + 1, voisins[0]});
for (int i = 1; i < sz(voisins) - 1; ++i)
inters.pb({voisins[i - 1] + 1, voisins[i]});
inters.pb(TOUT);
}
int iPere = -1;
for (int i = 0; i < sz(voisins); ++i){
if (inters[i].x <= source && source <= inters[i].y){
iPere = i;
continue; //si on est sur le pere
}
if (inters[i].x <= dest && dest <= inters[i].y)
return voisins[i];
}
return voisins[iPere];
}
