题目描述

当然我们的孩子喜欢在动物园散步。动物园有 $n$ 个区域，编号从 $1$ 到 $n$。第 $i$ 个区域里有 $a_{i}$ 只动物。此外，动物园里有 $m$ 条道路，每条道路连接两个不同的区域。动物园本身是连通的，也就是说，利用这些道路可以从任意一个区域到达任意另一个区域。

我们的孩子非常聪明。假设他想从区域 $p$ 走到区域 $q$。他会考虑从 $p$ 到 $q$ 的所有简单路径。对于每一条路径，他会写下该路径上所有区域中动物数量的最小值。我们记这些数中最大的为 $f(p,q)$。最后，孩子会选择一条使他记录下 $f(p,q)$ 的路径。

孩子参观完动物园以后，他思考了一个问题：所有 $p,q$（$p \ne q$）对下的 $f(p,q)$ 的平均值是多少？你能帮他回答这个问题吗？

输入格式

第一行包含两个整数 $n$ 和 $m$。
第二行包含 $n$ 个整数：$a_{1},a_{2},...,a_{n}$。
接下来的 $m$ 行，每行包含两个整数 $x_{i}$ 和 $y_{i}$，表示一条连接区域 $x_{i}$ 和 $y_{i}$ 的道路。

所有道路均为双向，每对区域之间最多只存在一条道路。

输出格式

输出一个实数，表示 $\text{average}=\frac{\sum_{p\ne q} f(p,q)}{n(n-1)}$。

如果你的答案的相对误差或绝对误差不超过 $10^{-4}$，则被认为是正确的。

4 3
10 20 30 40
1 3
2 3
4 3

16.666667

3 3
10 20 30
1 2
2 3
3 1

13.333333

7 8
40 20 10 30 20 50 40
1 2
2 3
3 4
4 5
5 6
6 7
1 4
5 7

18.571429

说明 / 提示

考虑第一个样例。有 $12$ 种不同的情况：

• $p=1,q=3,f(p,q)=10$。
• $p=2,q=3,f(p,q)=20$。
• $p=4,q=3,f(p,q)=30$。
• $p=1,q=2,f(p,q)=10$。
• $p=2,q=4,f(p,q)=20$。
• $p=4,q=1,f(p,q)=10$。

另外 $6$ 种情况与上述对称。平均值为 $\frac{200}{12} \approx 16.666667$。

再看第二个样例。有 $6$ 种不同的情况：

• $p=1,q=2,f(p,q)=10$。
• $p=2,q=3,f(p,q)=20$。
• $p=1,q=3,f(p,q)=10$。

另外 $3$ 种情况与上述对称。平均值为 $\frac{80}{6} \approx 13.3333$。

由 ChatGPT 5 翻译

数据范围

（$2 \le n \le 10^5$；$0 \le m \le 10^5$）

（$0 \le a_{i} \le 10^5$）

（$1 \le x_{i},y_{i} \le n$；$x_{i} \ne y_{i}$）