Надійність мережі

Незважений граф задано. Кожне ребро графа може зникнути з певною ймовірністю. Обчисліть ймовірність того, що граф, який залишився, буде зв'язним.

Вхідні дані

Перша строка містить три цілі числа 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) означає ребро, яке з'єднує вершини v_i та u_i.

Вихідні дані

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

Приклади