Exploration urbaine – Regional event 2015

Level 6

É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

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
9 7
0 1
0 2
0 3
3 4
4 5
5 6
6 7
Sample output
8 8
Note

schema.png

Si on démarre dans la salle numéro 8, on est bloqué et on ne pourra explorer en tout qu'une salle. Sinon, on pourra explorer les 8 salles de 0 à 7, et le trajet optimal est de longueur 8.

Sample input
9 6
0 1
0 2
0 3
4 5
5 6
6 7
Sample output
4 3

Submit your solution

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