Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2869

Time Limit: 3 Seconds      Memory Limit: 32768 KB

Managers of Tehran International Fair are experiencing the most difficult working days during the last 6 years. Recently, they are faced with a large number of requests to hire some of the fair halls. Each request consists of a list of candidate halls from which only one is needed by the requester, and the period of time during which the hall is needed to be hired. When there are only a few requests, the task of scheduling and allocating the halls to the requests are easy, but now, due to the large number of requests and the several overlaps between the requests, the task has been grown to an exhausting and time-consuming scheduling problem.

As a result, they have hired you, as a professional programmer, to write a program which is capable of doing the task of allocating halls to the requests automatically. What you are needed to do as the first phase of this project is to write a program that only indicates whether all the requests can be fulfilled with respect to the available resources or not.


The first line of input contains a single integer T, which is the number of test cases. Each test case starts with a line containing one integer 1 <= R <= 12 which is the number of requests, followed by R lines, each of which containing the description of a single request. A request is a line containing the positive integers A B K H1 H2 ... Hk, in which the period [A, B] (1 <= A <= B <= 10000) indicates the period during which a hall is needed, K indicates the number of candidate halls and 1 <= H1,..., Hk <= 8 are the indices of the candidate halls from which a hall is to be allocated to that request.


For each test case, your program should output a line containing the phrase "YES" if there is a way to fulfill all the requests. Otherwise it should output "NO".

Sample Input

1 2 1 1
2 3 1 1
2 4 2 1 3
3 6 2 1 2
3 6 2 1 3
5 7 2 2 3

Sample Output


Author: Babak Behsaz
Source: AUT Contest 1
Submit    Status