DZY любит физику, больше всего ему нравится считать плотность.
Плотность есть почти у всего, даже у графа. Определим плотность неориентированного графа, вершины и ребра которого имеют некоторые значения, следующим образом:
, где
v — сумма значений вершин графа,
e — сумма значений ребер графа.
Как-то раз DZY раздобыл граф G. Теперь он хочет найти связный порожденный подграф G' данного графа с максимальной плотностью.
Порожденный подграф G'(V', E') графа G(V, E) — это граф, удовлетворяющий условиям:
-
; - ребро
тогда и только тогда, когда 
, а ребро 
; - значение ребра в G' равняется значению соответствующего ребра в G, аналогичное утверждение верно и для вершин.
Помогите DZY найти порожденный подграф с максимальной плотностью. Обратите внимание на то, что выбранный вами порожденный подграф должен быть связанным.
Выходные данные
Выведите действительное число, обозначающее ответ, с абсолютной или относительной погрешностью не более 10 - 9.
Примечание
В первом примере можно выбрать либо пустой подграф, либо подграф с единственной вершиной 1.
Во втором примере оптимальное решение — выбрать весь граф.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 0
1
|
0.000000000000000
|
|
2
|
2 1
1 2
1 2 1
|
3.000000000000000
|
|
3
|
5 6
13 56 73 98 17
1 2 56
1 3 29
1 4 42
2 3 95
2 4 88
3 4 63
|
2.965517241379311
|