Dues festes P82271


Statement
 

pdf   zip

thehtml

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 ≤ 104, que els noms són paraules amb entre una i sis lletres minúscules, 1 ≤ m ≤ 5a, xy, 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.

Public test cases
  • Input

    5 edgar tomas omer anna ivet
    4
    anna tomas
    omer anna
    edgar ivet
    edgar anna
    
    3 x y z
    3
    x y
    y z
    x z
    
    3 a b c
    1
    c a
    

    Output

    SI anna ivet
    NO
    SI a b
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++