Pentes à vélo

Emil souhaite voyager de la ville 1 à la ville n à vélo, mais les routes qui relient ces villes lui posent un problème. Chaque route présente une pente, soit en montée, soit en descente. Lorsque Emil passe d’une route en montée à une route en descente (ou l’inverse), il doit changer de vitesse pour garder une conduite confortable. Emil veut déterminer le nombre minimal de changements de vitesse dont il aura besoin pendant son trajet de la ville 1 à la ville n.

Affichez le nombre minimal de changements de vitesse nécessaires pour qu’Emil effectue son voyage de la ville 1 à la ville n.

Entrée

La première ligne contient deux entiers séparés par un espace, n et m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000), qui représentent respectivement le nombre de villes et le nombre de routes.

Les m lignes qui suivent contiennent chacune deux entiers séparés par un espace et (, ), indiquant qu’il existe une route reliant les villes et . La route allant de à est en montée, donc celle allant de à est en descente.

Sortie

Le programme doit afficher un seul entier, correspondant au nombre minimal de changements de vitesse qu’Emil devra effectuer pour aller de la ville 1 à la ville n.

Exemples