Une espèce unique et énigmatique connue sous le nom de Nuko habite un archipel dans une partie reculée du monde. L'archipel peut être modélisé par $N$ îles, numérotées de $0$ à $N - 1$, reliées par $M$ ponts. Chaque pont $i$ relie deux îles, $U[i]$ et $V[i]$, pour tout $0 \leq i \leq M - 1$, dans les deux sens. Il est possible d'atteindre n'importe quelle île depuis n'importe quelle autre île. Chaque pont relie deux îles distinctes, et aucun pont ne relie la même paire d'îles.

Dans les temps anciens, les Nukos habitaient uniquement l'île $0$. Cependant, suffisamment de temps a passé et les Nukos se sont propagés sur toutes les îles. Chaque fois qu'un groupe de Nukos traverse un pont vers une nouvelle île, ils évoluent, donnant naissance à une sous-espèce différente de celle présente sur l'île précédente. Plus précisément, pour l'île $j$, pour tout $0 \leq j \leq N - 1$, les Nukos sont de la sous-espèce $s_j$, qui est égale au nombre minimal de ponts qu'il faut traverser pour atteindre l'île $j$ depuis l'île $0$. Par exemple, les Nukos sur l'île $0$ sont de la sous-espèce $0$.

Vous êtes un voyageur cherchant à aller des îles $A$ à $B$ en utilisant les ponts. Il est garanti que $A \neq B$. Lorsque vous êtes sur une île, vous rencontrerez inévitablement la sous-espèce de Nukos qui y vit. Comme chaque sous-espèce a ses propres coutumes, et que s'adapter à des coutumes différentes peut être problématique, votre objectif est de choisir un chemin qui minimise le nombre de sous-espèces de Nuko distinctes que vous rencontrez.

Pouvez-vous déterminer le nombre minimal de sous-espèces de Nuko distinctes que vous devez rencontrer lors d'un voyage de l'île $A$ à $B$ ?

Détails d'implémentation

Vous devez implémenter la procédure suivante.

int min_distinct(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V)

• $N$ : le nombre d'îles.
• $M$ : le nombre de ponts.
• $A$ : le point de départ de votre voyage.
• $B$ : le point d'arrivée de votre voyage.
• $U$, $V$ : tableaux de longueur $M$ décrivant les ponts.
• Cette procédure doit retourner le nombre minimal de sous-espèces de Nuko distinctes que vous devez rencontrer.

Contraintes

• $2 \le N \le 5\,000\,000$.
• $1 \le M \le 5\,000\,000$.
• $0 \le A, B \le N - 1$.
• $A \neq B$.
• $0 \le U[i], V[i] \le N - 1$, pour tout $0 \leq i \leq M - 1$.
• $U[i] \neq V[i]$, pour tout $0 \leq i \leq M - 1$.
• $(U[i], V[i]) \neq (U[j], V[j])$ et $(U[i], V[i]) \neq (V[j], U[j])$, pour tout $0 \leq i, j \leq M-1$ et $i \neq j$.
• Il est garanti qu'il est possible d'atteindre n'importe quelle île depuis n'importe quelle autre île.

Sous-tâches

1. (4 points) $A = 0$, $N \le 100\,000$, $M \le 100\,000$.
2. (4 points) $M = N - 1$, $N \le 100\,000$, $M \le 100\,000$.
3. (6 points) $N \le 300$, $M \le 300$.
4. (8 points) $N \le 4\,000$, $M \le 4\,000$.
5. (22 points) $N \le 4\,000$, $M \le 1\,000\,000$.
6. (14 points) $N \le 100\,000$, $M \le 100\,000$.
7. (5 points) $N \le 300\,000$, $M \le 300\,000$.
8. (5 points) $N \le 500\,000$, $M \le 500\,000$.
9. (32 points) Aucune contrainte supplémentaire.

Remarque : Pour la sous-tâche 9, le correcteur seul est garanti de consommer 1500ms sur la limite de temps de 4500ms.

Exemples

Considérez les appels suivants.

min_distinct(5, 5, 2, 4, [0, 1, 2, 3, 4], [1, 2, 3, 4, 0])

Les îles peuvent être illustrées comme ci-dessous, avec des ombrages différents représentant différentes sous-espèces de Nuko.

Pour l'exemple 1, le chemin optimal est $2-3-4$. Les sous-espèces de Nuko rencontrées sont $1$ et $2$. Par conséquent, cet appel doit retourner $2$.

min_distinct(8, 9, 4, 7, [0, 0, 0, 1, 1, 2, 2, 6, 7], [1, 2, 3, 4, 5, 5, 6, 3, 3])

Les îles peuvent être illustrées comme ci-dessous, avec des ombrages différents représentant différentes sous-espèces de Nuko.

Pour l'exemple 2, le chemin optimal est $4-1-5-2-6-3-7$. Les sous-espèces de Nuko rencontrées sont $1$ et $2$. Par conséquent, cet appel doit retourner $2$.

min_distinct(15, 17, 3, 7,
              [0, 1, 2, 3, 4, 13, 12, 12, 11, 10, 10, 9, 8, 7, 6, 8, 0],
              [1, 2, 3, 4, 13, 12, 1, 11, 10, 9, 5, 8, 7, 6, 5, 14, 14])

Pour l'exemple 3, le nombre minimal de sous-espèces de Nuko distinctes que vous devez rencontrer lors d'un voyage de l'île $3$ à l'île $7$ est $3$. Par conséquent, cet appel doit retourner $3$.

Correcteur d'exemple

Format d'entrée :

N M A B
U[0] V[0]
U[1] V[1]
...
U[M - 1] V[M - 1]

Format de sortie :

Un entier représentant la valeur de retour de min_distinct.