我们的孩子当然喜欢在动物园里散步。动物园有 n 个区域,编号从 1 到 n。第 i 个区域包含 ai 动物。动物园里还有m条路,每条路连接两个不同的区域。当然,动物园是相连的,因此您可以通过道路从任何其他区域到达动物园的任何区域。
我们的孩子很聪明。想象一下孩子想要从 p 区到 q 区。首先,他考虑从 p 到 q 的所有简单路线。对于每条路线,孩子写下数字,该数字等于路线区域中动物的最小数量。让我们将最大的书面数字表示为 f(p, q)。最后,孩子选择其中一条路线并记下值 f(p, q)。
孩子参观完动物园后,他思考这个问题:所有对 p, q (p ≠ q) 的 f(p, q) 的平均值是多少?你能回答他的问题吗?
输入
第一行包含两个整数 n 和 m (2 ≤ n ≤ 105; 0 ≤ m ≤ 105)。第二行包含 n 个整数:a1, a2, ..., an (0 ≤ ai ≤ 105)。然后m行,每行包含两个整数xi和yi(1≤xi,yi≤n;xi≠yi),表示xi和yi区域之间的道路。
所有道路都是双向的,每对区域最多由一条道路连接。
输出
输出一个实数 — $$\frac{\sum_{p,q,p\neq q} f(p,q)}{n(n-1)}$$ 的值。
如果答案的相对或绝对误差不超过 10 - 4,则认为答案是正确的。
示例
输入 #1
4 3 10 20 30 40 1 3 2 3 4 3
输出 #1
16.666667
输入 #2
3 3 10 20 30 1 2 2 3 3 1
输出 #2
13.333333
输入 #3
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
输出 #3
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例与上述对称。平均值为 $$(10+20+30+10+20+10)\times 2\over 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例与上述对称。平均值为$$(10+20+10)\times2\over6\approx13.333333$$。