2002 Canadian Computing Competition, Stage 2

Day 2, Problem 2: Connect the Campus

Many new buildings are under construction on the campus of the University of Polkaroo. The university has hired bricklayers, electricians, plumbers, and a computer programmer. A computer programmer? Yes, you have been hired to ensure that each building is connected to every other building (directly or indirectly) through the campus network of communication cables.

We will treat each building as a point specified by an x-coordinate and a y-coordinate. Each communication cable connects exactly two buildings, following a straight line between the buildings. Information travels along a cable in both directions. Cables can freely cross each other, but they are only connected together at their endpoints (at buildings).

You have been given a campus map which shows the locations of all buildings and existing communication cables. You may not alter the existing cables. Determine where to install new communication cables so that all buildings are connected. Of course, the university wants you to minimize the amount of new cable that you use.

Input

The input file describes one test case. The first line contains the number of buildings N (1 ≤ N ≤ 750). The buildings are labelled from 1 to N. The next N lines give the x and y coordinates of the buildings. These coordinates are integers with absolute values at most 10000. No two buildings occupy the same point.

Finally there is a line containing the number of existing cables M (0 ≤ M ≤ 1000) followed by M lines describing the existing cables. Each cable is represented by two integers: the building numbers which are directly connected by the cable. There is at most one cable directly connecting each pair of buildings.

Output

For each new cable you plan to construct, output a line containing the numbers of the two buildings that will be joined by the cable. Also output the total length of the new cables that you plan to use, rounded to two decimal places. If there is more than one possible minimal solution you may output any such solution.

Sample Input

4
103 104
104 100
104 103
100 100
1
4 2

Sample Output

4.41
3 2
1 3

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 256M
Added: Apr 18, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)