Условие:
На плане фей всё не так, как в материальном плане. Ты можешь идти часами с, казалось бы, одной и той же скоростью, но в один день ты пройдешь лишь пару холмов, а в другой — покроешь путь сквозь несколько стран, просто потому что у Лорда фей было разное настроение в эти дни. То же касается и существ этого мира, а также, как логично предположить, растений. Тебе в руки попал отросток древа Ночи (или древа Клипот), кора которого является основой зелья бессмертия, но только при удачной/правильной конфигурации дерева. Суть в том, что древо растет непредсказуемо, но лишь определенные конфигурации ветвей распределяют древесный сок так, чтобы кора приобрела свои целебные свойства. Из древних записей ты понимаешь, что на N-й год жизни древо достигает пика своей силы, а также конфигурацию, которая сделает его пригодным для зелья. Тебе необходимо определить, с какой вероятностью нам удастся изготовить зелье бессмертия.
Как растет древо:
Рост начинается с корня (вершина 0). На первый год из этого корня отрастает ребро с вершиной 1 на конце.
На следующий год рост вновь начинается с корня и следует по правилу. Находясь на данной вершине, из которой исходит k ребер, все выходные ребра нумеруются числа от 1 до k, после чего равновероятно выбирается число m от 1 до k + 1. Если m = k + 1, то отрастает новое ребро из данной вершины. Если m <= k, то происходит переход вверх вдоль ребра с соответствующим номером, где повторяется описанная процедура, пока рано или поздно новая ветвь не появится. Появление новой ветки означает, что возраст древа увеличился на 1.
Пункт 2 повторяется, пока древо не достигает возраста N. (N — количество ребер, N + 1 — количество вершин)
Формат ввода
Вводится целое число N — возраст древа (< 10). Далее вводятся пары целых чисел через пробел (от 0 до N). Каждая пара задает ребро ориентированного графа в направлении от левого числа к правому. 0 считаем корнем дерева, а все ребра считаем ветвями.
Формат вывода
Выведите дробное число P (действительное число от 0 до 1) — вероятность появления древа именно с данной конфигурацией без округления.
Пример 1
Ввод
2
0 1
1 2
Вывод
0.5
Пример 2
Ввод
3
0 1
0 2
1 3
Вывод
0.583333333
Примечание
Все конфигурации древа, которые можно сопоставить путем перенумерации ветвей, но не меняя корень, считаются одинаковыми.
Примеры двух одинаковых графов:
\nAlt Text Alt Text
