Connecting the Farms

Farmer John has acquired several new farms and wants to connect them with roads so that he can travel between any two farms. Each farm is represented by a point \((x_i, y_i)\) in the plane, and some roads already connect some of the farms. Your task is to add additional roads such that all farms become connected while minimizing the total length of the new roads.

Formally, you are given \(n\) points with coordinates \((x_i,y_i)\) for \(i=1,2,\ldots,n\). The points are numbered from 1 to \(n\). There are \(m\) preexisting roads, where the \(j\)-th road connects farm \(u_j\) and farm \(v_j\). You need to add new roads so that the resulting network is connected, and the sum of the lengths of the new roads is minimized. The length between two farms \(i\) and \(j\) is the Euclidean distance, given by \(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\).

Input Constraints:

• \(1 \leq n \leq 1000\)
• \(0 \leq x_i, y_i \leq 10^6\)
• \(1 \leq m \leq 1000\)

Note: If there is already a road between two farms, you do not pay any extra cost to traverse that connection.

inputFormat

The first line contains two integers \(n\) and \(m\), the number of farms and the number of preexisting roads.

The next \(n\) lines each contain two integers \(x_i\) and \(y_i\), representing the coordinates of the \(i\)-th farm.

The following \(m\) lines each contain two integers \(u_j\) and \(v_j\), indicating that there is an existing road connecting farms \(u_j\) and \(v_j\).

outputFormat

Output a single line containing the total length of the additional roads that need to be built, formatted to two decimal places.

sample

4 1
0 0
0 1
1 0
1 1
1 2

2.00