P2872 [USACO07DEC] Building Roads S

Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms. Each of the $N (1 \le N \le 1,000)$ farms (conveniently numbered $1 \sim N$) is represented by a position $(X_i, Y_i)$ on the plane $(0 \le X_i \le 1,000,000; 0 \le Y_i \le 1,000,000)$. Given the preexisting $M$ roads $(1 \le M \le 1,000)$ as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.

* Line $1$: Two space-separated integers: $N$ and $M$. * Lines $2 \sim N+1$: Two space-separated integers: $X_i$ and $Y_i$. * Lines $N+2 \sim N+M+2$: Two space-separated integers: $i$ and $j$, indicating that there is already a road connecting the farm $i$ and farm $j$.

* Line $1$: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.

### 数据规模与约定 对于 $100\%$ 的整数，$1 \le n,m \le 1000$，$1 \le x_i,y_i \le 10^6$，$1 \le u_i,v_i \le n$。 ### 说明 Translated by 一只书虫仔。