{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"平坦国家Flatopia是完全平坦的。不幸的是,Flatopia有一个非常糟糕的公共高速公路系统。Flatopia政府意识到了这个问题,并已经修建了一些连接一些重要城镇的高速公路。然而,仍然有一些城镇是无法通过高速公路到达的。必须修建更多的高速公路,以便可以在任意两个城镇之间驾驶而不离开高速公路系统。\r\u003cbr\u003e\r\u003cbr\u003eFlatopia的城镇编号从1到N,第i个城镇的位置由笛卡尔坐标(xi, yi)给出。每条高速公路连接两个城镇。所有高速公路(无论是原有的还是要修建的)都是直线,因此它们的长度等于城镇之间的笛卡尔距离。所有高速公路可以双向使用。高速公路可以自由交叉,但驾驶员只能在位于两条高速公路末端的城镇之间切换高速公路。\r\u003cbr\u003e\r\u003cbr\u003eFlatopia政府希望最小化修建新高速公路的成本。但是,他们希望保证每个城镇都可以从任何其他城镇通过高速公路到达。由于Flatopia非常平坦,高速公路的成本始终与其长度成正比。因此,最便宜的高速公路系统将是使总高速公路长度最小化的系统。\r\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入由两部分组成。第一部分描述了该国所有城镇,第二部分描述了已经修建的所有高速公路。\r\u003cbr\u003e\r\u003cbr\u003e输入文件的第一行包含一个整数N(1 \u003c\u003d N \u003c\u003d 750),表示城镇的数量。接下来的N行每行包含两个整数xi和yi,用空格分隔。这些值给出了第i个城镇的坐标(i从1到N)。坐标的绝对值不会大于10000。每个城镇都有一个唯一的位置。\r\u003cbr\u003e\r\u003cbr\u003e接下来一行包含一个整数M(0 \u003c\u003d M \u003c\u003d 1000),表示已建成的高速公路数量。接下来的M行每行包含一对用空格分隔的整数。这两个整数给出已经通过高速公路连接的城镇编号对。每对城镇最多由一条高速公路连接。\r\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"为了连接所有城镇并使新修建的高速公路总长度最小,对于应该修建的每条新高速公路,输出一行。每条高速公路应通过打印连接该高速公路的城镇编号,用空格分隔。\r\u003cbr\u003e\r\u003cbr\u003e如果不需要修建新的高速公路(所有城镇已经连接),则应创建输出文件,但内容为空。\r\u003cbr\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e9\r\n1 5\r\n0 0 \r\n3 2\r\n4 5\r\n5 1\r\n0 4\r\n5 2\r\n1 2\r\n5 3\r\n3\r\n1 3\r\n9 7\r\n1 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 6\r\n3 7\r\n4 9\r\n5 7\r\n8 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}