Plan de métro – Regional event 2003

Level 4

ENONCE

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 retourner 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.

CONTRAINTES

  • 1 \<= S \<= 1000, où S est l'identifiant d'une station de métro.

  • 1 \<= N \<= 200, où N est le nombre de stations de métro.

  • 1 \<= C \<= 1000, où C est le nombre de couples de stations reliées.

ENTREE

  • La première ligne de l'entrée contient un entier : l'identifiant de la station de métro dont on part.

  • La deuxième ligne de l'entrée contient un entier : le nombre C de couples de stations de métro reliées.

  • Les C lignes suivantes contiennent chacune deux entiers, séparés par un 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.

Runtime constraints

Maximum memory usage
8000 kilobytes
Maximum execution time
250 milliseconds

Input/output samples

Sample input
1
14
1 3
3 42
42 57
57 270
42 566
566 245
245 556
556 924
924 516
556 432
556 461
461 640
640 632
432 589
Sample output
7

Submit your solution

You have to register or log in to be able to submit your solution.