В Семи Королевствах n городов и n - 1 дорога, каждая дорога соединяет два города, и возможно достичь каждый город из каждого, передвигаясь по дорогам.
Теон и Яра Грейджой начинают путешествовать на лошади по дорогам из первого города. Из-за тумана они не видят, куда лошадь их везет. Когда лошадь входит в город (в том числе в первый), она направляется в один из городов, соединенных с ним. Но это странная лошадь, поэтому она пойдет только в город, в котором до этого не была. Она идет равновероятно в каждый из таких городов и останавливается, если таких городов нет.
Пусть длина каждой дороги 1. Путешествие начинается в городе 1. Чему равно математическое ожидание длины их путешествия? Формально, математическое ожидание — это ожидаемое (то есть среднее) значение. Подробнее можно прочесть по ссылке https://ru.wikipedia.org/wiki/Математическое_ожидание.
Выходные данные
Выведите одно число — математическое ожидание длины путешествия. Путешествие начинается в городе 1.
Ваш ответ будет считаться правильным, если его абсолютная или относительная точность не превосходит 10 - 6.
А именно, если ваш ответ равен a, а ответ жюри равен b, то ваш ответ будет зачтен, если 
.
Примечание
В первом примере путешествие может закончиться в городах 3 или 4 с равной вероятностью. Расстояние до городов 3 и 4 равно 1 и 2, соответственно, поэтому матожидание длины равно 1.5.
Во втором примере путешествие может закончиться в городах 4 или 5. Расстояние до обоих городов 2, поэтому матожидание равно 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
1 3
2 4
|
1.500000000000000
|
|
2
|
5
1 2
1 3
3 4
2 5
|
2.000000000000000
|