Problem D: 高速公路

Problem D: 高速公路

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 270  Solved: 58
[Submit] [Status] [Web Board] [Creator:]

Description

岛国完全平坦。不幸的是,岛国的公共高速公路系统非常糟糕。岛国政府意识到了这个问题,并且已经建造了一些连接一些最重要城镇的高速公路。但是,仍有一些城镇无法通过高速公路抵达。有必要建造更多的高速公路,以便能够在不离开高速公路系统的情况下在任何一对城镇之间行驶。
岛国城镇的编号从1到N,城镇i的位置由笛卡尔坐标(xi,yi)给出。每条高速公路连接两个城镇。所有高速公路(原始高速公路和要建造的高速公路)都遵循直线,因此它们的长度等于城镇之间的笛卡尔距离。所有高速公路都可以在两个方向使用。高速公路可以自由地相互交叉,但司机只能在位于两条高速公路尽头的小镇的高速公路之间切换。
岛国政府希望最大限度地降低建设新高速公路的成本。但是,他们希望保证每个城镇都可以从其他城镇到达公路。由于岛国是平坦,高速公路的成本总是与其长度成正比。因此,最便宜的高速公路系统将是最小化总公路长度的系统。

Input

输入包括两部分。第一部分描述了该国的所有城镇的坐标,第二部分描述了所有已建成的高速公路。
输入文件的第一行包含一个整数N(1 <= N <= 750),表示城镇数量。接下来的N行每行包含两个整数,xi和yi由空格分隔。、表示第i个城镇的坐标(对于i从1到N)。坐标的绝对值不超过10000。
下一行包含一个整数M(0 <= M <= 1000),表示现有高速公路的数量。接下来的M行每行包含一对由空格分隔的整数。这两个整数给出了一对已经通过高速公路连接的城镇号码。每对城镇至少由一条高速公路连接。

Output

输出为:每建造一条高速公路就打印出这条高速公路两端的编号,中间用空格隔开按(所有的编号按字典序最小输出)
如果不需要建立新的高速公路(所有城镇都已连接),则输出“Zero”。

Sample Input Copy

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

Sample Output Copy

1 6
3 7
3 8
4 9
5 7