← 返回题目列表

Codeforces · 1250/K

K. 投影仪

中文机器翻译题面 查看原题

今天,近似科学学院将举办 $$$n$$$ 讲座和 $$$m$$$ 研讨会。第 $$$i$$$ 讲座从 $$$a_i$$$ 开始,到 $$$b_i$$$ 结束(正式来说,讲座的时间跨越区间 $$$[a_i, b_i)$$$,右界不包括在内)。第 $$$j$$$ 研讨会从 $$$p_j$$$ 开始,到 $$$q_j$$$ 结束(同样,研讨会的时间跨越区间 $$$[p_j, q_j)$$$,右界不包括在内)。

学院有编号从 $$$1$$$ 到 $$$x$$$ 的 $$$x$$$ 高清投影仪和编号从 $$$x + 1$$$ 到 $$$x + y$$$ 的普通投影仪 $$$y$$$。投影仪的分布方式应满足以下条件:

- 每次讲座均使用高清投影仪;
- 每个研讨会使用一些投影仪(普通或高清);
- 一台投影仪(普通或高清)只能在同一时刻的一个活动中使用;
- 如果为某个活动选择了投影仪,则该投影仪将在整个活动期间使用;
- 如果投影仪开始时间不早于当前事件结束,则可以在后续事件中重复使用投影仪。

您将找到这样的投影仪分布(如果存在)。

再次注意,事件时间范围的右边界不包括在内:如果某个事件恰好在另一个事件结束时开始,则可以重复使用投影仪(假设它立即传送到事件位置)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 300$$$) — 测试用例的数量。

每个测试用例都以包含四个整数的行开始 $$$n, m, x, y$$$ ($$$0 \le n, m, x, y \le 300$$$; $$$n+m>0$$$, $$$x + y > 0$$$) — 分别为讲座数量、研讨会数量、高清投影仪数量和普通投影仪数量。

接下来的 $$$n$$$ 行描述讲座。每行包含两个整数 $$$a_i$$$、$$$b_i$$$ ($$$1 \le a_i < b_i \le 10^6$$$) — 第 $$$i$$$ 课程的开始时间(含)和结束时间(不含)。

接下来的 $$$m$$$ 行描述了研讨会。每行包含两个整数 $$$p_j$$$、$$$q_j$$$ ($$$1 \le p_j < q_j \le 10^6$$$) — 第 $$$j$$$ 次研讨会的开始时间(含)和结束时间(不含)。

输出

对于每个测试用例,如果可以分发投影仪以满足所有要求,则打印“是”,否则打印“否”。

如果答案是肯定的,则输出包含 $$$n + m$$$ 整数的附加行。前$$$n$$$个整数应不小于$$$1$$$且不大于$$$x$$$,其中第$$$i$$$个应为第$$$i$$$次讲座中使用的高清投影仪的索引。最后$$$m$$$个整数应不小于$$$1$$$且不大于$$$x + y$$$,其中第$$$j$$$个应为第$$$j$$$次研讨会使用的投影机索引。如果有多个答案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

YES
2 1 4 3 
YES
2 1

输入 #2

3
1 2 1 1
3 4
2 4
1 3
3 4 2 3
5 7
1 3
1 7
4 8
2 5
1 6
2 8
0 1 1 0
1 1000000

输出 #2

YES
1 2 1 
NO
YES
1