Exploration urbaine – Épreuve régionale 2015

Énoncé¶

Vous avez été invité à une visite nocturne des catacombes. Pour planifier cette visite, vous disposez d'une carte sur laquelle ont été marquées des salles et des couloirs. Très peu de couloirs sont renseignés : ils relient tous deux salles entre elles, et vous remarquez que chaque couloir est la seule façon d'aller entre les deux salles qu'il relie (c'est-à-dire que si un couloir entre A et B a été indiqué sur la carte, aucun autre chemin passant par des couloirs indiqués ne part de A pour arriver à B ; comme dans un labyrinthe, quoi).

Vous pouvez choisir la salle de départ et d'arrivée de votre expédition, dans le but de pouvoir visiter le plus grand nombre de salles possible avant de remonter à la surface, en empruntant les couloirs connus. (Rappelez-vous qu'une salle n'est pas forcément joignable à partir d'une autre, le choix de la salle de départ est déterminant !) De plus, parmi plusieurs choix de trajets pour visiter le nombre maximum de salles, vous voulez privilégier ceux qui vous font parcourir une distance moindre dans les couloirs (on supposera que tous les couloirs ont la même longueur).

À partir de la carte, écrivez un programme pour vous indiquer quel est le nombre de salles visitées, et la longueur (en nombre de fois où vous devez traverser un couloir) du parcours optimal.

Entrée¶

• Sur la première ligne, deux entiers séparés d'une espace : le nombre n de salles, puis le nombre m de couloirs

• Sur chacune des m lignes suivantes, deux entiers k et l indiquant la présence d'un couloir entre la salle k et la salle l. Les salles sont numérotées de 0 à n-1

Sortie¶

Le nombre de salles visitées, suivi de la longueur du parcours optimal, séparés par une espace.

Contraintes¶

• 1 <= n <= 5000
• 0 <= l <= 5000