Надежность сети

Дан неориентированный граф. Каждое его ребро может исчезнуть с заданной вероятностью. Необходимо вычислить вероятность того, что оставшийся граф останется связным.

Входные данные

Первая строка содержит три целых числа N (1 ≤ N ≤ 14), M (0 ≤ M ≤ 100) и P (0 ≤ P ≤ 100), разделенные пробелом. Здесь N — количество вершин, M — количество рёбер, а P — вероятность в процентах.

Следующие M строк описывают рёбра графа. Каждая строка содержит два целых числа v_i и u_i (1 ≤ v_i, u_i ≤ N), которые обозначают ребро, соединяющее вершины v_i и u_i.

Выходные данные

Выведите вероятность того, что оставшийся граф будет связным. Ваша программа может выводить любое количество знаков после десятичной точки, но абсолютная ошибка не должна превышать 10^{-9}.

Примеры