Coursier de Midgard – Qualification 2024

Niveau 5 ⋅ Validation weight: 25%

Énoncé

Les dieux nordiques doivent appliquer un protocole de communication très spécial pour prévenir les dieux des villes qui se font détruire par le serpent Jörmungandr. Ce protocole, nommé HTTP (pour Hel's Transcendent Transfer Protocol), a pour objectif de s'assurer que tous les dieux reçoivent le message une seule fois.

Jøsëf est recruté par les dieux pour mettre en place le protocole de communication.

Le protocole est le suivant :

  • Le message d'abord placé dans une enveloppe, puis remise dans les mains d'un dieu quelconque.
  • Cette enveloppe ne peut ensuite transiter qu'entre deux dieux qui partagent le même prénom ou le même nom.
  • Cette enveloppe doit passer dans les mains de tous les dieux.
  • Chaque dieu ne peut recevoir le message qu'une unique fois
  • Si au transfert précédent le message est passé entre deux dieux qui ont le même prénom, alors au transfert suivant le message doit passer entre deux dieux qui ont le même nom, et inversement.

Étant donné la liste des noms des dieux, proposez si possible un chemin de dieu en dieu qui respecte le protocole HTTP.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de dieux.
  • Sur les lignes suivantes, une liste de N éléments : dieux, liste des prénoms et noms des dieux séparés par un espace.
    • Une ligne par élément de la liste : une chaine de 32 caractères ou moins.

Sortie

S'il n'existe aucun chemin qui permette de faire passer le message par tous les dieux en respectant le protocole HTTP, afficher sur une ligne le message IMPOSSIBLE. Sinon, afficher, sur une ligne par dieu et dans l'ordre désiré, les noms complets des dieux par lesquels le message doit passer. Si plusieurs solutions existent, afficher n'importe laquelle d'entre elles.

Contraintes

  • $1 \le N \le 20$
  • Deux dieux ne peuvent pas partager le même prénom et le même nom

Contraintes de performance

  • $1 \le N \le 100\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
Alof Amno
Baikik Brok
Alof Brok
Exemple de sortie
Alof Amno
Alof Brok
Baikik Brok
Commentaire

Ici, le message est initialement remis au dieu Alof Amno. Ensuite, Alfo Amno transfère le message à Alof Brok, qui partage son prénom. Finalement, Alof Brok transfère le message à Baikik Brok, qui partage son nom.

Notez que Baikik Brok → Alof Brok → Alof Amno était également une solution valide.

Exemple d'entrée
5
0dric Apik
0dric Brik
1dric Apik
1dric Brik
Tonb Apik
Exemple de sortie
Tonb Apik
1dric Apik
1dric Brik
0dric Brik
0dric Apik
Commentaire

Ici, le message est initialement remis à Tonb Apik. Ensuite :

  • Tonb Apik transfère le message à 1dric Apik, qui partage le même nom
  • 1dric Apik transfère le message à 1dric Brik, qui partage le même prénom
  • 1dric Brik transfère le message à 0drik Brik, qui partage le même nom
  • Finalement, 0dric Brik transfère le message à 0dric Apik, qui partage le même prénom.

Remarquez que ces trois autres solutions existent :

  • Tonb Apik → 0dric Apik → 0dric Brik → 1dric Brik → 1dric Apik
  • 0dric Apik → 0dric Brik → 1dric Brik → 1dric Apik → Tonb Apik
  • 1dric Apik → 1dric Brik → 0dric Brik → 0dric Apik → Tonb Apik
Exemple d'entrée
3
Seche Plusplus
Seche Seche
Seche Harpe
Exemple de sortie
IMPOSSIBLE
Commentaire

Ici, il est impossible de faire passer le message à tous les dieux tout en respectant le protocole HTTP.

En effet, pour faire passer le message aux trois dieux, on devrait alterner entre "faire passer le message entre deux dieux qui ont le même prénom", puis "faire passer le message entre deux dieux qui ont le même nom", ou inversement.

Cependant, aucun dieu ne possède le même nom. Il est donc impossible de faire passer le message à tout le monde.