描述

平坦岛国Flatopia的地势完全平坦。不幸的是，Flatopia的公共高速公路系统非常落后。Flatopia政府意识到了这个问题，并且已经修建了一些连接重要城镇的高速公路。然而，仍有一些城镇无法通过高速公路到达。因此，有必要修建更多的高速公路，使得任意两个城镇之间都可以通过高速公路系统相互到达。

Flatopia的城镇编号从1到N，城镇i的位置由笛卡尔坐标(xi, yi)给出。每条高速公路恰好连接两个城镇。所有高速公路（包括已建的和待建的）均为直线，因此其长度等于城镇之间的笛卡尔距离。所有高速公路均可双向通行。高速公路可以相互交叉，但司机只能在两个高速公路的端点城镇处切换路线。

Flatopia政府希望最小化修建新高速公路的成本。然而，他们需要确保每个城镇都可以通过高速公路到达其他任何城镇。由于Flatopia地势平坦，高速公路的成本总是与其长度成正比。因此，最经济的高速公路系统是总长度最短的系统。

输入

输入由两部分组成。第一部分描述该国所有城镇，第二部分描述所有已修建的高速公路。

输入文件的第一行包含一个整数N（1 ≤ N ≤ 750），表示城镇的数量。接下来的N行每行包含两个整数xi和yi，用空格分隔。这些值给出了第i个城镇的坐标（i从1到N）。坐标的绝对值不超过10000。每个城镇的位置是唯一的。

接下来一行包含一个整数M（0 ≤ M ≤ 1000），表示已存在的高速公路数量。接下来的M行每行包含一对用空格分隔的整数。这两个整数表示已经通过高速公路连接的一对城镇编号。每对城镇之间最多有一条高速公路。

输出

对于需要修建的每条新高速公路，输出一行，包含两个用空格分隔的城镇编号，表示应修建连接这两个城镇的高速公路。修建这些高速公路后，所有城镇将以最小的总新修高速公路长度实现连通。

如果不需要修建新的高速公路（所有城镇已经连通），则输出文件应为空。

输入数据 1

9
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3
1 3
9 7
1 2

输出数据 1

1 6
3 7
4 9
5 7
8 3

来源

Northeastern Europe 1999