#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 = 1000, INDEFINI = -1;
int deb[N], fin[N];
int temps = 0;
bool vu[N];
vector<int> voisins[N];
void dfs(int noeud){
vu[noeud] = true;
deb[noeud] = temps++;
for (int voisin : voisins[noeud]){
if (vu[voisin]) continue;
dfs(voisin);
}
fin[noeud] = temps;
}
vector<int> label(int nNoeuds, int labelMax, vector<int> u, vector<int> v) {
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);
vector<int> labels(nNoeuds);
for (int i = 0; i < nNoeuds; ++i)
labels[i] = deb[i] * N + fin[i];
return labels;
}
int find_next_station(int source, int dest, vector<int> voisins) {
int debSource = source/N, finSource = source%N;
int debDest = dest/N, finDest = dest%N;
vector<pii> inters;
for (int i = 0; i < sz(voisins); ++i)
inters.pb({voisins[i]/N, voisins[i]%N});
int iPere = -1;
for (int i = 0; i < sz(voisins); ++i){
if (inters[i].x <= debDest && finDest <= inters[i].y)
return voisins[i];
if (inters[i].x <= debSource && finSource <= inters[i].y)
iPere = i;
}
return voisins[iPere];
}
