#P18697. Exam Requirements
Exam Requirements
Exam Requirements
大学本学期的考试即将开始。共有 场考试,第 场考试从时刻 持续到时刻 ,包括两个端点。要通过一场考试,必须完整参加其整个过程;完整出席即可通过。
你只能参加彼此时间不重叠的考试。严格来说,只有当闭区间 和 不相交时,才能同时参加考试 。例如, 与 相交, 与 也相交,而 与 不相交。
毕业需要满足 条要求。每条要求给出两场不同的考试 ,要求你至少通过其中一场。
判断是否存在一种参加考试的方案,既满足全部毕业要求,又只参加时间互不重叠的考试。输出 YES 或 NO,区分大小写。
输入格式
第一行包含整数 ,表示测试用例数。
对于每个测试用例:
- 第一行包含两个整数 ;
- 接下来 行,第 行包含两个整数 ,表示考试 的起止时刻;
- 接下来 行,每行包含两个整数 ,表示必须至少通过考试 中的一场。
数据范围
- ;
- ;
- ;
- ;
- 每条要求满足 且 ;
- 所有测试用例的 之和不超过 ;
- 所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,单独输出一行:若可以满足所有要求并毕业,输出 YES;否则输出 NO。输出区分大小写。
样例输入
2
3 1
1 5
2 7
10 11
2 1
3 3
1 5
2 7
5 7
1 2
2 3
3 1
样例输出
YES
NO
样例说明
第一个测试用例有三场考试和一条要求。只要通过考试 或考试 中的任意一场,就能满足要求并毕业。
第二个测试用例中,三场考试两两时间重叠,因此最多只能参加一场。要满足给出的三条要求,却至少需要通过其中两场,所以无法毕业。