Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Halls
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1769Accepted: 507

Description

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.

Input

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 ≤ AB ≤ 10000) indicates the period during which a hall is needed, K indicates the number of candidate halls and 1 ≤ H1H2 ... ≤ HK ≤8 are the indices of the candidate halls from which a hall is to be allocated to that request.

Output

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

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

Sample Output

NO
YES

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator