Plan de métro – Épreuve régionale 2003

Énoncé¶

On vous donne en paramètre la description d'un plan de métro, sous la forme d'une liste des couples de stations entre lesquelles il existe une ligne de métro sur laquelle ces deux stations sont consécutives. On peut donc se déplacer entre ces deux stations sans passer par une quelconque autre station.

On vous indique une station de départ, et vous devez trouver la station la plus éloignée de cette station, lorsque l'on s'y rend en métro, c'est-à dire celle qui nécessite de passer par le plus grand nombre de stations intermédiaires. On ne tient pas compte du temps passé aux éventuelles correspondances.

Les stations de métro sont identifiées par des numéros. Tout ce qu'on vous donne, ce sont des couples de nombres, identifiant deux stations reliées directement.

Votre fonction doit renvoyer le nombre de stations intermédiaires par lesquelles il faut passer pour se rendre à la station la plus éloignée de la station de départ. Attention : il ne faut pas compter la station de départ, ni la station d'arrivée, mais uniquement celles se situant entre les deux.

Entrée¶

• La première ligne de l'entrée contient un entier $S$ : l'identifiant de la station de métro dont on part.
• La deuxième ligne de l'entrée contient un entier $C$ : le nombre de couples de stations de métro reliées.
• Les $C$ lignes suivantes contiennent chacune deux entiers, séparés par une espace : les identifiants de deux stations de métro reliées directement.

Sortie¶

Vous devez écrire une ligne sur la sortie :

• Un entier, indiquant le nombre de stations intermédiaires par lesquelles il faut passer pour aller vers la station la plus éloignée.

Contraintes¶

• $1 \le S, C \le 1\,000$