Projectors

题意翻译

有$n$堂讲课，$m$次研讨会，$x$个高清投影仪和$y$个普通投影仪。 每堂讲课必须使用一个高清投影仪，而研讨会可以使用普通或高清投影仪。 第$i$堂讲课时间在$[a_i,b_i)$，第$i$次研讨会在时间在$[p_i,q_i)$，一个投影仪每个时刻只能用在一个地方，且在使用完毕后才会归还。 构造为每节讲课/研讨会分配一个投影仪的方案。 $n,m,x,y \leq 300, a_i,b_i,p_i,q_i \leq 10^6$

题目描述

There are $ n $ lectures and $ m $ seminars to be conducted today at the Faculty of Approximate Sciences. The $ i $ -th lecture starts at $ a_i $ and ends at $ b_i $ (formally, time of the lecture spans an interval $ [a_i, b_i) $ , the right bound is exclusive). The $ j $ -th seminar starts at $ p_j $ and ends at $ q_j $ (similarly, time of the seminar spans an interval $ [p_j, q_j) $ , the right bound is exclusive). There are $ x $ HD-projectors numbered from $ 1 $ to $ x $ and $ y $ ordinary projectors numbered from $ x + 1 $ to $ x + y $ available at the faculty. Projectors should be distributed in such a way that: - an HD-projector is used in each lecture; - some projector (ordinary or HD) is used in each seminar; - a projector (ordinary or HD) can only be used in one event at the same moment of time; - if a projector is selected for an event, it is used there for the whole duration of the event; - a projector can be reused in some following event, if it starts not earlier than current event finishes. You are to find such distribution of projectors, if it exists. Again, note that the right bound of the event's time range is not inclusive: if some event starts exactly when another event finishes, the projector can be reused (suppose that it is instantly transported to the location of the event).

输入输出格式

输入格式

The first line contains an integer $ t $ ( $ 1 \le t \le 300 $ ) — the number of test cases. Each test case starts with a line containing four integers $ n, m, x, y $ ( $ 0 \le n, m, x, y \le 300 $ ; $ n+m>0 $ , $ x + y > 0 $ ) — the number of lectures, the number of seminars, the number of HD projectors and the number of ordinary projectors, respectively. The next $ n $ lines describe lectures. Each line contains two integers $ a_i $ , $ b_i $ ( $ 1 \le a_i < b_i \le 10^6 $ ) — the start time (inclusive) and finish time (exclusive) of the $ i $ -th lecture. The next $ m $ lines describe seminars. Each line contains two integers $ p_j $ , $ q_j $ ( $ 1 \le p_j < q_j \le 10^6 $ ) — the start time (inclusive) and finish time (exclusive) of the $ j $ -th seminar.

输出格式

For each test case, print YES if it is possible to distribute projectors in order to meet all requirements, or NO otherwise. In case of positive answer, output one additional line containing $ n + m $ integers. The first $ n $ integers should be not less than $ 1 $ and not greater than $ x $ , and the $ i $ -th of them should be the index of HD projector used in the $ i $ -th lecture. The last $ m $ integers should be not less than $ 1 $ and not greater than $ x + y $ , and the $ j $ -th of them should be the index of projector used in the $ j $ -th seminar. If there are multiple answers, print any of them.

输入输出样例

输入样例 #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