Algoland and Berland

题意翻译

很久以前，Algoland和Berland是一个国家，但那个时代早已过去。现在它们是两个国家，但他们的城市散布在一个共同的领土上。 所有城市都表示为一个平面直角坐标系的一个点。Algoland由 $a$ 个城市组成，编号从 $1$ 到 $a$。Algoland第 $i$ 个城市的坐标为 $(xa_i,ya_i)$ 。同样的，Berland由 $b$ 个城市组成，编号从 $1$ 到 $b$。Berland第 $j$ 个城市的坐标是 $(xb_j,yb_j)$ 。保证两个国家的 $a+b$ 个城市里没有三个城市在一条直线上。 作为联合两国的第一步，Berland决定修建几条双向的高速公路。每条高速公路将是一条线段，从Berland的一个城市开始，到Algoland的一个城市结束。除了高速公路的起点或终点，高速公路不能在任何一点上相互交叉。此外，高速公路必须连接所有 $a+b$ 个城市。这意味着人们可以通过高速公路从任何一个城市到达任何其他的城市。请注意，所有的高速公路都是双向的，这意味着人们可以在每条高速公路上双向行驶。 每一个Berland城市的市长都分配了一个预算来建造从这个城市出发的高速公路。因此，你会得到数 $r_1,r_2,\dots,r_b$ ，其中 $r_j$ 是要从第 $j$ 个Berland城市开始的高速公路的数量。市长们分配的预算是非常紧张的，只有建设所有高速公路必要的代价。也就是 $r_1+r_2+\dots+r_b=a+b-1$ 。 请你帮助Berland建设高速公路，有以下几个要求： - 每条高速公路都是一条连接Berland城市和Algoland城市的线段。 - 没有任何两条高速公路有交点，除了交点是两条公路的起点或终点。 - 高速公路必须连接所有 $a+b$ 个城市。 - 有 $r_j$ 条高速公路从第 $j$ 个Berland城市开始。 ### 输入格式 本题有多组测试数据。 第一行输入一个整数 $t$ $(1\le t\le3000)$ ，代表有 $t$ 组测试数据。 每个测试数据的第一行有两个整数，分别为 $a$ 和 $b$ 。 第二行有 $b$ 个整数，第 $i$ 个整数表示 $r_i$ $(1\le r_i\le a)$ 。 接下来的 $a$ 行，每行两个整数 $xa_i,ya_i$ 。 再接下来的 $b$ 行，每行两个整数 $xb_i,yb_i$ 。 具体意义见上文描述。 ### 输出格式 对于每个测试数据，第一行输出`YES`或`NO`，代表能否满足要求。 如果能满足要求，输出 $a+b-1$ 行，每行有两个整数 $j$ 和 $i$，表示从第 $j$ 个Berland城市往第 $i$ 个Algoland城市建设一条高速公路。如果有多组方法，请输出其中的一个

题目描述

Once upon a time Algoland and Berland were a single country, but those times are long gone. Now they are two different countries, but their cities are scattered on a common territory. All cities are represented as points on the Cartesian plane. Algoland consists of $ a $ cities numbered from $ 1 $ to $ a $ . The coordinates of the $ i $ -th Algoland city are a pair of integer numbers $ (xa_i, ya_i) $ . Similarly, Berland consists of $ b $ cities numbered from $ 1 $ to $ b $ . The coordinates of the $ j $ -th Berland city are a pair of integer numbers $ (xb_j, yb_j) $ . No three of the $ a+b $ mentioned cities lie on a single straight line. As the first step to unite the countries, Berland decided to build several bidirectional freeways. Each freeway is going to be a line segment that starts in a Berland city and ends in an Algoland city. Freeways can't intersect with each other at any point except freeway's start or end. Moreover, the freeways have to connect all $ a+b $ cities. Here, connectivity means that one can get from any of the specified $ a+b $ cities to any other of the $ a+b $ cities using freeways. Note that all freeways are bidirectional, which means that one can drive on each of them in both directions. Mayor of each of the $ b $ Berland cities allocated a budget to build the freeways that start from this city. Thus, you are given the numbers $ r_1, r_2, \dots, r_b $ , where $ r_j $ is the number of freeways that are going to start in the $ j $ -th Berland city. The total allocated budget is very tight and only covers building the minimal necessary set of freeways. In other words, $ r_1+r_2+\dots+r_b=a+b-1 $ . Help Berland to build the freeways so that: - each freeway is a line segment connecting a Berland city and an Algoland city, - no freeways intersect with each other except for the freeway's start or end, - freeways connect all $ a+b $ cities (all freeways are bidirectional), - there are $ r_j $ freeways that start from the $ j $ -th Berland city.

输入输出格式

输入格式

Input contains one or several test cases. The first input line contains a single integer number $ t $ ( $ 1 \le t \le 3000 $ ) — number of test cases. Then, $ t $ test cases follow. Solve test cases separately, test cases are completely independent and do not affect each other. Each test case starts with a line containing space-separated integers $ a $ and $ b $ ( $ 1 \le a, b \le 3000 $ ) — numbers of Algoland cities and number of Berland cities correspondingly. The next line contains $ b $ space-separated integers $ r_1, r_2, \dots, r_b $ ( $ 1 \le r_b \le a $ ) where $ r_j $ is the number of freeways, that should start in the $ j $ -th Berland city. It is guaranteed that $ r_1+r_2+\dots+r_b=a+b-1 $ . The next $ a $ lines contain coordinates of the Algoland cities — pairs of space-separated integers $ xa_i, ya_i $ ( $ -10000 \le xa_i, ya_i \le 10000 $ ). The next $ b $ lines contain coordinates of the Berland cities — pairs of space-separated integers $ xb_i, yb_i $ ( $ -10000 \le xb_i, yb_i \le 10000 $ ). All cities are located at distinct points, no three of the $ a+b $ cities lie on a single straight line. Sum of values $ a $ across all test cases doesn't exceed $ 3000 $ . Sum of values $ b $ across all test cases doesn't exceed $ 3000 $ .

输出格式

For each of the $ t $ test cases, first print "YES" if there is an answer or "NO" otherwise. If there is an answer, print the freeway building plan in the next $ a+b-1 $ lines. Each line of the plan should contain two space-separated integers $ j $ and $ i $ which means that a freeway from the $ j $ -th Berland city to the $ i $ -th Algoland city should be built. If there are multiple solutions, print any.

输入输出样例

输入样例 #1

2
2 3
1 1 2
0 0
1 1
1 2
3 2
4 0
1 1
1
0 0
0 1

输出样例 #1

YES
2 2
1 2
3 2
3 1
YES
1 1