Dues festes P82271

Voleu fer una festa amb tots els vostres amics, però lamentablement alguns es tenen mania entre si. Per tant, heu decidit fer dues festes en lloc d’una, invitant cada amic a exactament una festa, i evitant que dues persones que es tinguin mania vagin a la mateixa festa. Ho podreu aconseguir?

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre d’amics a, seguit dels seus a noms, tots diferents i en qualsevol ordre. Segueix el nombre de manies m, i els m parells d’amics x i y que es tenen mania.

Suposeu 2 ≤ a ≤ 10⁴, que els noms són paraules amb entre una i sis lletres minúscules, 1 ≤ m ≤ 5a, x ≠ y, que tant x com y apareixen a la lista d’a amics, i que cap mania apareix més d’una vegada.

Sortida

Escriviu una línia per a cada cas. Si no hi ha solució, escriviu “NO”. Altrament, escriviu “SI” seguit dels noms dels participants a qualsevol de les dues festes, en qualsevol ordre. Si hi ha més d’una solució, trieu la que vulgueu. Seguiu exactament el format dels exemples.