Problem E
Transportation Planning

As a city planner, you have spent a lot of time building a set of two-way roads so that people can get from anywhere in the city to anywhere else just by driving on the roads. Now that that’s done, you are concerned with how much time commuters spend on the road each day, and how you can reduce this. You have modeled the city as a set of intersections connected by roads. You have come up with a measure of the total commute time: it is the sum of the shortest driving time between all pairs of intersections in the city using the available roads. You have gotten the city to agree to build one more road between two existing intersections, and you want to add a single road that will reduce this measure of commute time the most. Which road should you add?

Input

Input consists of up to $100$ test cases. Each test case begins with a line containing $2 \le n \le 100$, which is the number of intersections. Intersections are numbered $0$ to $n-1$. The next $n$ lines describe the unique locations of the intersections, given in order from $0$ to $n-1$. Each location is an $x~ y$ integer coordinate pair, where $-500 \le x, y \le 500$. The following line contains an integer $0 \le m \le n(n-1)/2$ indicating the number of roads that currently exist, followed by $m$ lines describing the roads. Each road is described as a pair of intersection numbers. Within a test case each road is unique. The commute time for a road is the number of seconds it takes to travel between the road’s endpoints at constant speed of one unit per second. It is guaranteed that all intersections are connected by some sequence of roads. Input ends when $n$ is zero.

Output

For each city configuration, print out which pair of intersections should be connected by a road to minimize the total commute time measure, and give the new commute time measure. If the solution is not unique, then give the solution that uses the lowest-numbered intersections (with preference that the first intersection is the lowest number possible, followed by the preference that the second intersection is the lowest number possible). If no road addition will improve things, indicate that instead. Your answers should have a relative error of at most $0.0001$.

5
25 65
41 53
37 90
25 20
18 57
4
3 4
0 2
2 3
1 3
4
5 43
31 32
49 90
0 85
4
1 2
2 3
0 3
0 1
3
0 0
100 0
0 100
3
0 1
1 2
0 2
0

adding 0 4 reduces 834.3724683377 to 537.3468586201
adding 0 2 reduces 339.9989622408 to 315.4205424223
no addition reduces 341.4213562373