Вам дано дерево (неориентированный связный граф без циклов) и целое число \(s\).
Ваня хочет как-то поставить веса на всех ребрах дерева, так что все веса неотрицательные вещественные числа, которые в сумме дают \(s\). При этом он хочет, чтобы диаметр получившегося после расстановки весов дерева был как можно меньше. Диаметром будем называть максимальную сумму весов ребер, лежащих на пути между какими-то двумя вершинами дерева.
Найдите минимальный возможный диаметр, который мог у него получиться.
Выходные данные
Выведите минимальный диаметр дерева, который мог получиться при какой-то расстановке неотрицательных весов на ребра этого дерева, которые в сумме дают \(s\).
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить \(10^{-6}\).
А именно: пусть ваш ответ равен \(a\), а ответ жюри \(b\). Ваш ответ будет засчитан, если \(\frac {|a-b|} {max(1, b)} \leq 10^{-6}\).
Примечание
В первом примере необходимо расставить веса так:
Легко видеть, что диаметр такого дерева будет равен \(2\). Можно доказать, что это минимально возможный диаметр, который можно получить, как-то расставив веса.
Вo втором примере необходимо расставить веса так:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 2
1 3
1 4
|
2.000000000000000000
|
|
2
|
6 1
2 1
2 3
2 5
5 4
5 6
|
0.500000000000000000
|
|
3
|
5 5
1 2
2 3
3 4
3 5
|
3.333333333333333333
|