Coursier d'Asgard – Qualification 2024

Niveau 5 ⋅ Validation weight: 30%

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

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

Le protocole est le suivant :

  • Le message est d'abord placé dans une enveloppe, puis remis dans les mains d'un dieu quelconque, appelé le dieu initial.
  • 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 entre les mains de tous les dieux.
  • Un dieu doit toujours transmettre l'enveloppe à un autre dieu qui ne l'a pas encore reçu, si possible.
  • Si un dieu ne peut plus transmettre l'enveloppe à un autre dieu qui ne l'a pas encore reçu, il doit redonner l'enveloppe au dieu qui lui a initialement donné.

Étant donné la liste (non ordonnée) des paires de dieux s'étant transmis au moins une fois l'enveloppe, déterminez s'il est possible que les transmissions aient respecté le protocole HTTP, et si oui, déterminez qui a pu être le dieu initial.

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.
  • Sur la ligne suivante, un entier : M, nombre de passations du message.
  • Sur les lignes suivantes, une liste de M éléments : passations, liste des échanges de message entre les dieux, les noms complets des deux dieux séparés par un espace.
    • Une ligne par élément de la liste : une chaine de 64 caractères ou moins.

Notez que les transmissions indiquées dans l'entrée ne respectent pas forcément l'ordre des transmissions effectuées.

Notez aussi que seuls les deux dieux impliqués dans chaque transmissions sont indiqués, dans un ordre quelconque. Le premier dieu de chaque paire n'est pas forcément celui qui a remis le message au second dieu, l'inverse est possible.

Sortie

Si le message n'a pas été passé en respectant le protocole, afficher sur une ligne le message NON. Sinon, afficher OUI sur une ligne, puis, en affichant un nom par ligne, le nom de tous les dieux ayant pu être dieu initial.

Vous pouvez afficher le nom des dieux dans l'ordre de votre choix.

Contraintes

  • $2 \le N \le 20$
  • $1 \le M \le 50$
  • Deux dieux ne peuvent pas partager le même prénom et le même nom
  • Aucune paire de dieux ne sera indiquée en double dans l'entrée.

Contraintes de performance

  • $2 \le N \le 3\,000$
  • $1 \le M \le 3\,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
5
Gudrir Bjorg
Gudrir Idunn
Gudrir Alvis
Harvardr Idunn
Harvardr Alvis
4
Gudrir Bjorg Gudrir Idunn
Harvardr Alvis Harvardr Idunn
Gudrir Idunn Gudrir Alvis
Gudrir Idunn Harvardr Idunn
Exemple de sortie
OUI
Gudrir Alvis
Commentaire

Le message envoyé par Jøsëf doit passer par 5 dieux différents :

  • Gudrir Bjorg
  • Gudrir Idunn
  • Gudrir Alvis
  • Harvardr Idunn
  • Harvardr Alvis

Supposons que Gudrir Alvis soit le dieu initial. Alors :

  • Gudrir Alvis peut transmettre l'enveloppe à Gudrir Idunn, qui possède le même prénom.
  • Ensuite, Gudrir Idunn peut transmettre l'enveloppe à Gudrir Bjorg, qui possède le même prénom.
  • Ici, Gudrir Bjorg ne peut plus transmettre l'enveloppe à un autre dieu qui n'a pas encore reçu l'enveloppe. Il la remet donc à Gudrir Idunn, de qui il tient l'enveloppe.
  • Gudrir Idunn transmet alors l'enveloppe à Harvardr Idunn, qui possède le même nom de famille.
  • Enfin, Harvardr Idunn transmet l'enveloppe à Harvardr Alvis, qui possède le même prénom.

Ce message est alors passé d'un dieu à un autre 4 fois :

  • Il a été d'abord échangé entre Gudrir Alvis et Gudrir Idunn,
  • Il a été ensuite échangé entre Gudrir Idunn et Gudrir Bjorg,
  • Il a été ensuite échangé entre Gudrir Bjorg et Gudrir Idunn une seconde fois,
  • Il a été ensuite échangé entre Gudrir Idunn et Harvardr Idunn,
  • Il a été enfin échangé entre Harvardr Idunn et Harvardr Alvis.

Les quatre transmissions distinctes correspondent aux transmissions listées en entrée, cela montre donc que Gudrir Alvis a pu être dieu initial tout en respectant le protocole HTTP.

Au contraire, il est impossible qu'un autre dieu ait pu être dieu initial tout en respectant le protocole HTTP au vu des échanges indiqués. Par exemple, si Gudrir Bjorg était dieu initial, alors :

  • Les transmissions indiquent que Gudrir Bjorg aurait transmis le message à Gudrir Idunn, qui partage son prénom,
  • Ensuite, Gudrir Idunn a pu transmettre le message soit à Gudrir Alvis, soit à Harvardr Idunn.
  • Si Gudrir Idunn a transmis le message à Gudrir Alvis, alors Gudrir Alvis aurait dû retransmettre le message à Harvardr Alvis, qui n'a pas encore reçu le message. Or, cet échange n'a pas eu lieu.
  • Si Gudrir Idunn a transmis le message à Harvardr Idunn, alors Harvardr Idunn aurait dû retransmettre le message à Harvardr Alvis, qui aurait ensuite dû transmettre le message à Gudrir Alivs. Ce dernier échange n'a pas eu lieu.

Cela montre qu'il est impossible que Gudrir Bjorg ait pu être le dieu initial.

Exemple d'entrée
6
Dan Randolf
Idun Viggo
Dan Torleif
Ari Viggo
Vidar Viggo
Dan Viggo
5
Dan Viggo Vidar Viggo
Ari Viggo Dan Viggo
Dan Torleif Dan Randolf
Dan Viggo Idun Viggo
Dan Randolf Dan Viggo
Exemple de sortie
NON
Commentaire

Dans cet exemple, le message envoyé par Jøsëf doit passer par 6 dieux différents :

  • Dan Randolf
  • Idun Viggo
  • Dan Torleif
  • Ari Viggo
  • Vidar Viggo
  • Dan Viggo

Parmi les transmissions indiquées, on remarque que le message est passé, entre autres :

  • entre Dan Viggo et Vidar Viggo
  • entre Dan Viggo et Ari Viggo
  • entre Dan Viggo et Idun Viggo

Peu importe le dieu de départ, cela rentre toujours en conflit avec les spécifications du protocole HTTP.

Par exemple, si parmi ces quatre dieux, Dan Viggo avait reçu le message en premier, alors Ari Viggo, Vidar Viggo et Idun Viggo auraient dû se faire passer le message entre eux, plutôt que de redonner le message à Dan Viggo qui a déjà reçu le message.