Lazy employees P76991


Statement
 

pdf   zip

thehtml

Xavier works at a company with n employees (between 0 and n−1) and q tasks to do (between 0 and q−1). Every task has a list of all the employees that can do it. Note that it is allowed that more than one employee does the same task, and that the same employee does more than one task. There are ℓ ‍employees that are really lazy, and they will not work under any circumstances. Moreover, there are e eccentric employees. Each such employee x has a list of employees such that x will only accept to work if at least one of the employees of his list also works. Under all those constraints, is it possible to do all the tasks of the company?

Input

Input consists of several cases. Every case begins with n and q. Follow q lines: the i-th line starts with a number mi between 1 and n, followed by a list of mi different employees that can do task i. Follow ℓ and the ℓ lazy employees. Finally, we have information about the eccentricities: First we have e, followed by e lines, each one with an eccentric employee ‍x, a number rx between 1 and n−1, followed by a list of the rx employees in x’s list (all different and ≠ x). Assume that n and q are between 1 and 104, ∑mi ≤ 5q, ∑rx ≤ 5n, and 0 ≤ ℓ + en. The lazy and the eccentric employees are all different.

Output

For each case, print “YES” if all the tasks can be done, and “NO” otherwise.

Public test cases
  • Input

    1 1
    1  0
    0
    0
    
    5 2
    4  3 2 1 0
    5  0 1 2 3 4
    2  1 0
    2
    2 2  0 1
    3 2  2 1
    
    3 2
    1  1
    2  1 0
    1  2
    2
    1 1  0
    0 1  1
    

    Output

    YES
    NO
    YES
    
  • Information
    Author
    Edgar Moreno
    Language
    English
    Official solutions
    C++
    User solutions
    C++