Demi-finale 2003, épreuve machine - Plan de métro

DIFFICULTE

LIMITE DE MEMOIRE

8000 ko

LIMITE DE TEMPS

250 ms

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.

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

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

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.

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

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

7