CF1250K Projectors

今天，在“近似科学”学院将举办 $n$ 场讲座和 $m$ 场研讨会。第 $i$ 场讲座从 $a_i$ 开始，到 $b_i$ 结束（即讲座的时间区间为 $[a_i, b_i)$，右端点不包含在内）。第 $j$ 场研讨会从 $p_j$ 开始，到 $q_j$ 结束（同样，研讨会的时间区间为 $[p_j, q_j)$，右端点不包含在内）。 学院有 $x$ 台 HD 投影仪，编号为 $1$ 到 $x$，以及 $y$ 台普通投影仪，编号为 $x+1$ 到 $x+y$。投影仪的分配需满足以下要求： - 每场讲座都必须使用一台 HD 投影仪； - 每场研讨会都必须使用一台投影仪（可以是 HD 或普通投影仪）； - 每台投影仪在同一时刻只能用于一场活动； - 一旦某台投影仪被分配给某场活动，则在该活动的整个持续时间内都要使用这台投影仪； - 如果某台投影仪分配给一场活动后，下一场活动的开始时间不早于当前活动的结束时间，则该投影仪可以被重复使用。 请判断是否存在一种投影仪的分配方案，使得所有要求都能满足。如果存在，请给出一种分配方案。 注意，活动时间区间的右端点是不包含的：如果一场活动的开始时间恰好等于另一场活动的结束时间，则投影仪可以被立即转移并复用。

第一行包含一个整数 $t$（$1 \le t \le 300$），表示测试用例的数量。 每个测试用例的第一行包含四个整数 $n, m, x, y$（$0 \le n, m, x, y \le 300$；$n+m>0$，$x+y>0$），分别表示讲座数量、研讨会数量、HD 投影仪数量和普通投影仪数量。 接下来的 $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$ 场研讨会的开始时间（包含）和结束时间（不包含）。

对于每个测试用例，如果存在满足要求的投影仪分配方案，输出 YES，否则输出 NO。 如果答案为 YES，则在下一行输出 $n+m$ 个整数。前 $n$ 个整数为 $1$ 到 $x$ 之间的数，第 $i$ 个数表示第 $i$ 场讲座使用的 HD 投影仪编号。后 $m$ 个整数为 $1$ 到 $x+y$ 之间的数，第 $j$ 个数表示第 $j$ 场研讨会使用的投影仪编号。若有多种方案，输出任意一种均可。

由 ChatGPT 4.1 翻译