The FME graph (2) P25513


Statement
 

pdf   zip

html

Lisbeth Salander (one of the main characters of the famous trilogy Millennium) is a crack mathematician, and therefore she is considering enrolling in the FME. As she likes both men and women, and she knows the FME graph, she is curious to know if it is possible that all the affairs have been between people of opposite sex. Help her!

Input

Input consists of several cases. Every case begins with the number of people n, followed by the information of each one: the name, the number mi of his or her affairs, and the mi names of the corresponding people. Assume that all the names are different, that for every pair of names x and y, if x is in the list of y then x exists and y is in the list of x, and that x is never in the list of x. Suppose 2 ≤ n ≤ 104, and that the total number of affairs is at most 2n.

Output

For every case, tell if it is possible that all the affairs have been between people of opposite sex.

Public test cases
  • Input

    6
    Alex 2 Felix Ivan
    Enric 2 Ivan Felix
    Ferran 1 Lander
    Lander 1 Ferran
    Ivan 2 Alex Enric
    Felix 2 Enric Alex
    4
    a 0
    d 2 b c
    b 2 d c
    c 2 d b
    

    Output

    yes
    no
    
  • Information
    Author
    Ferran Alet i Ivan Geffner
    Language
    English
    Translator
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++
    Event
    Vuitè Concurs de Programació de la FME
    Date
    2011-12-21