Restoring the Electrical Grid

Farmer John’s farm has experienced a vicious thunderstorm that has damaged some of the power wires connecting the electrical poles. There are (N) poles ((2 \le N \le 1000)) with integer coordinates ((x_i,y_i)) ((-100000 \le x_i, y_i \le 100000)). Some (W) wires ((1 \le W \le 10000)) remain intact, each connecting a pair of poles (P_i) and (P_j).

The goal is to re-establish electrical connection from pole (1) to pole (N). Farmer John may add new wires between any two poles provided that the Euclidean distance between them does not exceed (M) ((0.0 < M \le 200000.0)). The cost (or length) of a new wire is the Euclidean distance between the two poles. The already intact wires have zero cost. Determine the minimum total length of new wire required to restore the connection from pole (1) to pole (N). If it is impossible to connect under these conditions, output -1.

For example, consider a scenario with (N = 9), (W = 3) and (M = 2.0) where the poles are located as follows:

Pole 1: (0, 0)
Pole 2: (1, 0)
Pole 3: (2, 0)
Pole 4: (3, 0)
Pole 5: (2, 1)
Pole 6: (4, 1)
Pole 7: (4, 0)
Pole 8: (3, -1)
Pole 9: (5, 0)

and the remaining wires connect poles (1-2), (2-3), and (3-4). The optimal solution is to add new wires connecting pole 4 to pole 6 and pole 6 to pole 9. Their lengths are both (\sqrt{2}) (i.e. approximately 1.414213562) so the total added length is about (2.828427124).

inputFormat

The input begins with a line containing three values: (N) (the number of poles), (W) (the number of remaining wires), and (M) (the maximum permitted wire length for any new wire).

This is followed by (N) lines, each containing two integers representing the coordinates (x_i) and (y_i) of pole (i) (for (1 \le i \le N)).

Then there are (W) lines, each containing two integers (P_i) and (P_j) indicating that there is an intact (existing) wire between pole (P_i) and pole (P_j>.

outputFormat

Output a single line containing the minimum total length of new wire required to connect pole (1) to pole (N). Print the result with 9 decimal places. If it is impossible to establish the connection under the given constraints, output -1.

sample

3 1 5.0
0 0
3 4
6 8
1 2

5.000000000