#P18697. Exam Requirements

    ID: 18033 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-2-SAT线段树优化建图二分查找Kosaraju 算法SCC 判定可满足性

Exam Requirements

Exam Requirements

大学本学期的考试即将开始。共有 NN 场考试,第 ii 场考试从时刻 SiS_i 持续到时刻 EiE_i,包括两个端点。要通过一场考试,必须完整参加其整个过程;完整出席即可通过。

你只能参加彼此时间不重叠的考试。严格来说,只有当闭区间 [Si,Ei][S_i,E_i] 和 [Sj,Ej][S_j,E_j] 不相交时,才能同时参加考试 i,ji,j。例如,[1,3][1,3] 与 [2,5][2,5] 相交,[1,3][1,3] 与 [3,10][3,10] 也相交,而 [1,3][1,3] 与 [4,5][4,5] 不相交。

毕业需要满足 MM 条要求。每条要求给出两场不同的考试 A,BA,B,要求你至少通过其中一场。

判断是否存在一种参加考试的方案,既满足全部毕业要求,又只参加时间互不重叠的考试。输出 YES 或 NO,区分大小写。

输入格式

第一行包含整数 TT,表示测试用例数。

对于每个测试用例:

  • 第一行包含两个整数 N,MN,M;
  • 接下来 NN 行,第 ii 行包含两个整数 Si,EiS_i,E_i,表示考试 ii 的起止时刻;
  • 接下来 MM 行,每行包含两个整数 A,BA,B,表示必须至少通过考试 A,BA,B 中的一场。

数据范围

  • 1≤T≤1001\le T\le100;
  • 1≤N≤1000001\le N\le100000;
  • 0≤M≤1000000\le M\le100000;
  • 0≤Si≤Ei≤10000000000\le S_i\le E_i\le1000000000;
  • 每条要求满足 1≤A,B≤N1\le A,B\le N 且 A≠BA\ne B;
  • 所有测试用例的 NN 之和不超过 100000100000;
  • 所有测试用例的 MM 之和不超过 100000100000。

输出格式

对于每个测试用例,单独输出一行:若可以满足所有要求并毕业,输出 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

样例说明

第一个测试用例有三场考试和一条要求。只要通过考试 11 或考试 22 中的任意一场,就能满足要求并毕业。

第二个测试用例中,三场考试两两时间重叠,因此最多只能参加一场。要满足给出的三条要求,却至少需要通过其中两场,所以无法毕业。