Условие:
Тебе в руки попал отросток древа Ночи (или древа Клипот), кора которого является основой зелья бессмертия, но только при удачной/правильной конфигурации дерева. Суть в том, что древо растет непредсказуемо, но лишь определенные конфигурации ветвей распределяют древесный сок так, чтобы кора приобрела свои целебные свойства. Из древних записей ты понимаешь, что на 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) — вероятность появления древа именно с данной конфигурацией без округления.
