{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"曲奇国是一个岛国,它的交通建设非常糟糕,虽然有几个重要的城镇之间有高速公路可以互相达到,但其它的城镇却没有建设高速公路。现在UDK想在这些没有建设高速路的城镇之间建立高速路,以使得任意两个城镇可以互相到达并且建设高速公路的花费最小。因为UDK忘记了怎么算花费,所以请你编写个程序帮她算下如何使得每个城镇可以互相到达且花费最小。规定两个城镇间的最小花费就是两点的直线距离。"}},{"title":"Input","value":{"format":"HTML","content":"输入的第一行包含一个整数N,表示曲奇国有几个城镇。后面N行每行两个整数x,y,表示该城镇的坐标。然后是一个整数M,表示有M个城镇之间已经建立了高速公路,后面M行每行两个整数,u,v,表示u城镇到v城镇有路。"}},{"title":"Output","value":{"format":"HTML","content":"输出包括若干行,格式为u v,表示你帮UDK在u v两个城镇间建立了一条高速公路。__注意:输出顺序并不做要求__"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e9\n1 5\n0 0 \n3 2\n4 5\n5 1\n0 4\n5 2\n1 2\n5 3\n3\n1 3\n9 7\n1 2\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e1 6\n3 7\n4 9\n5 7\n8 3\n\u003c/pre\u003e"}},{"title":"","value":{"format":"HTML","content":""}}]}