CF437D.The Child and Zoo

Of course our child likes walking in a zoo. The zoo has n areas, that are numbered from 1 to n. The i-th area contains a__i animals in it. Also there are m roads in the zoo, and each road connects two distinct areas. Naturally the zoo is connected, so you can reach any area of the zoo from any other area using the roads.

Our child is very smart. Imagine the child want to go from area p to area q. Firstly he considers all the simple routes from p to q. For each route the child writes down the number, that is equal to the minimum number of animals among the route areas. Let's denote the largest of the written numbers as f(p, q). Finally, the child chooses one of the routes for which he writes down the value f(p, q).

After the child has visited the zoo, he thinks about the question: what is the average value of f(p, q) for all pairs p, q (p ≠ q)? Can you answer his question?

当然，我们的孩子喜欢在动物园里散步。动物园共有 $n$ 个区域，编号从 $1$ 到 $n$。第 $i$ 个区域中有 $a_i$ 只动物。此外，动物园内有 $m$ 条道路，每条道路连接两个不同的区域。显然，动物园是连通的，因此你可以通过道路从任意一个区域到达其他任意区域。

我们的孩子非常聪明。假设孩子想从区域 $p$ 走到区域 $q$。他首先考虑所有从 $p$ 到 $q$ 的简单路径（即不重复经过任何顶点的路径）。对每一条这样的路径，孩子会写下该路径所经过的所有区域中动物数量的最小值。我们将所有这些写下的数中的最大值记为 $f(p,\,q)$。最后，孩子会选择一条使得他写下的数值恰好等于 $f(p,\,q)$ 的路径。

孩子参观完动物园后，开始思考这样一个问题：对所有满足 $p \ne q$ 的区域对 $(p,\,q)$，$f(p,\,q)$ 的平均值是多少？你能回答他的这个问题吗？

The first line contains two integers n and m (2 ≤ n ≤ 105; 0 ≤ m ≤ 105). The second line contains n integers: _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 105). Then follow m lines, each line contains two integers x__i and y__i (1 ≤ x__i, y__i ≤ n; x__i ≠ y__i), denoting the road between areas x__i and y__i.

All roads are bidirectional, each pair of areas is connected by at most one road.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$；$0 \leq m \leq 10^5$）。第二行包含 $n$ 个整数：$a_1,\,a_2,\,\dots,\,a_n$（$0 \leq a_i \leq 10^5$）。接下来是 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i,\,y_i \leq n$；$x_i \neq y_i$），表示区域 $x_i$ 与区域 $y_i$ 之间有一条道路。

所有道路均为双向的，且任意两个区域之间至多只有一条道路。

Output a real number — the value of .

The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

输出一个实数——即 的值。

若答案的相对误差或绝对误差不超过 $10^{-4}$，则视为正确。

Consider the first sample. There are 12 possible situations:

• 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.

Another 6 cases are symmetrical to the above. The average is .

Consider the second sample. There are 6 possible situations:

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

Another 3 cases are symmetrical to the above. The average is .

考虑第一个样例。共有 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 种情况与上述情况对称。平均值为 。

考虑第二个样例。共有 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 种情况与上述情况对称。平均值为 。