Конечно, наш ребенок любит гулять по зоопарку. В зоопарке n вольеров, пронумерованных от 1 до n. В i-м вольере содержится ai животных. Также в зоопарке имеется m дорог, каждая дорога соединяет два различных вольера. Естественно, зоопарк связный, так что до любого вольера можно дойти по дорожкам от любого другого вольера.
Наш ребенок очень умный. Предположим, что ребенок хочет пройти из вольера p в вольер q. Сначала он рассматривает все простые пути от p до q. Для каждого пути ребенок выписывает число, равное минимальному количеству животных в вольерах на этом пути. Обозначим наибольшее записанное число как f(p, q). Наконец, ребенок выбирает один из путей, для которого выписанное значение равно f(p, q).
Ребенок уже посетил зоопарк, и теперь он размышляет: чему равно среднее значение f(p, q) для всех пар p, q (p ≠ q)? Можете ли вы ответить на его вопрос?
Выходные данные
Выведите вещественное число — значение 
.
Ответ будет считаться правильным, если его относительная или абсолютная погрешность не превышает 10 - 4.
Примечание
Рассмотрим первый пример. Существует 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 случая симметричны приведенному выше. Среднее значение равно 
.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
10 20 30 40
1 3
2 3
4 3
|
16.666667
|
|
2
|
3 3
10 20 30
1 2
2 3
3 1
|
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
|
18.571429
|