Prologin
2024
Énoncé¶
Pour que les habitants de la ville de Joseph aient de l'eau potable, le réseau d'aqueduc de la ville se doit d'être efficace. Il y a des années, les villes de Rome et Tivoli ont été reliées pour permettre une meilleure redistribution de l'eau.
Depuis quelques mois, les habitants de Rome ne sont plus satisfaits de la qualité de l'eau qui provient de Tivoli. Le responsable des aqueducs vous implore de l'aider et de trouver une solution à ce problème !
Après une intense réflexion, vous vous dites que la solution la plus simple est de séparer les aqueducs des deux villes. Bien entendu, Rome et Tivoli ne sont pas les seules à être interconnectées avec des aqueducs !
Entrée¶
- Sur la première ligne, $n$ le nombre de villes.
- Sur la deuxième ligne, $m$ le nombre d'aqueducs (ces aqueducs laissent passer l'eau dans les deux sens).
- Sur les $m$ lignes suivantes, deux entiers $a$ et $b$, représentant le lien entre la ville n°$a$ et la ville n°$b$ (les villes sont comptées de $0$ à $n-1$).
- Sur la ligne suivante, $H$ le numéro de la ville de Rome.
- Sur la ligne suivante, $T$ le numéro de la ville de Tivoli.
Sortie¶
Sur la premier ligne, $x$ le nombre minimal de lignes qu'il faut couper pour séparer Rome et Tivoli.
Sur les $x$ lignes suivantes, les aqueducs qui devront être détruits, sous la forme "$a$ $b$" avec $a$ et $b$ le numéro des villes qui sont connectées par l'aqueduc.
Si plusieurs réponses sont possibles, donnez en une seule de votre choix.
Contraintes¶
- $2 ≤ n ≤ 1000$
- $1 ≤ m ≤ 10^6$
