Description

一场猛烈的雷暴摧毁了农场电力网的一些电线！农夫约翰有一张所有 $N$ 根电线杆的地图（$2 \le N \le 1000$），这些电线杆被方便地编号为 $1\ldots N$，并位于整数平面坐标 $(x_i, y_i)$ 上（$-100000 \le x_i \le 100000, -100000 \le y_i \le 100000$）。

有 $W$ 根电线（$1 \le W \le 10000$）连接成对的电线杆 $P_i$ 和 $P_j$（$1 \le P_i \le N, 1 \le P_j \le N$）。

他需要从电线杆 $1$ 获取电力到电线杆 $N$（这意味着一些电线可以从电线杆 $1$ 通过某些中间电线杆传输到电线杆 $N$）。

给定 $N$ 根电线杆的位置和剩余电线的列表，确定恢复电力连接所需的最小电线长度，以便电力可以从电线杆 $1$ 流向电线杆 $N$。没有电线可以长于某个实数 $M$（$0.0 < M \le 200000.0$）。

例如，下面左侧是暴风雨后 $9$ 根电线杆和 $3$ 根电线的地图。对于这个任务，$M = 2.0$。最佳的电线连接方案是连接电线杆 $4$ 和 $6$，以及电线杆 $6$ 和 $9$。

   暴风雨后                  最优重新连接
3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                          /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                        /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                               |
0  1 . . . . . . . . .          0  1 . . . . . . . . .

   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9

总长度为 $1.414213562 + 1.414213562 = 2.828427124$。

分值：350

Input Format

第 $1$ 行：两个用空格分隔的整数：$N$ 和 $W$。

第 $2$ 行：一个实数：$M$。

第 $3\ldots N+2$ 行：每行包含两个用空格分隔的整数：$x_i$ 和 $y_i$。

第 $N+3\ldots N+2+W$ 行：两个用空格分隔的整数：$P_i$ 和 $P_j$。

Output Format

第 1 行：单独一行上的一个整数。如果无法恢复连接，输出 -1。否则，输出一个整数，该整数是恢复电力所需的总最小成本的 $1000$ 倍。不要进行任何四舍五入；截断结果乘积。

9 3 
2.0 
0 0 
0 1 
1 1 
2 1 
2 2 
3 2 
3 3 
4 1 
4 3 
1 2 
2 3 
3 4 

2828 

Hint

就像上面的图示一样。

如上所述。 （由 ChatGPT 4o 翻译）