시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Jak mawiają górale, są trzy rodzaje prawdy: święta prawda, tyż prawda i ... prawda. Najnowsze badania bajtockich logików potwierdzają to. Badają oni wyrażenia logiczne (formuły zdaniowe) o uproszczonej postaci nazywanej klauzulową. Postać klauzulowa wygląda następująco:

  • Formuły budujemy używając zmiennych logicznych x1x2,..., xn. Zmienne te mogą przyjmować wartości prawda lub fałsz.
  • Literał, to zmienna logiczna lub jej negacja, xi lub ¬xi (dla 1 ≤ i ≤ n).
  • Klauzula, to koniunkcja literałów, np. x4 ∧ ¬x2 ∧ x3.
  • Formuła, to alternatywa klauzul, np. (x1 ∧ ¬x2) ∨ (¬x1 ∧ x3) ∨ (¬x3).

Wartość formuły zależy od konkretnych wartości zmiennych. Wartości zmiennych określa się za pomocą funkcji nazywanej wartościowaniem, postaci f : {1, 2,..., n} → {prawda,fałsz}, gdzie f (i) jest wartością nadawaną zmiennej xi. Wszystkich możliwych wartościowań jest 2n. Dla konkretnego wartościowania, wartością danej formuły jest albo prawda albo fałsz.

Mówimy, że formuła jest prawdziwa, jeśli dla każdego wartościowania jej wartością jest prawda. Powiemy, że formuła jest fałszywa, jeżeli dla każdego wartościowania jej wartością jest fałsz. Często formuła nie jest ani prawdziwa, ani fałszywa, ale jej wartość zależy faktycznie od danego wartościowania. Prawdziwość formuły możemy określić jako ułamek (z zakresu od 0 do 1):

(liczba wartościowań, dla których wartością formuły jest prawda) / 2n

Liczba 1 odpowiada formułom prawdziwym, a 0 fałszywym.

Formuła:

(x1 ∧ ¬x1) ∨ (¬x2 ∧ ¬x3) ∨ (x3 ∧ x2)

jest prawdziwa dla czterech spośród ośmiu możliwych wartościowań. Tak więc jest ona prawdziwa w połowie.

입력

W pierwszym wierszu wejścia znajdują się dwie dodatnie liczby całkowite n i m, 1 ≤ n ≤ 100, 1 ≤ m ≤ 100, oddzielone pojedynczym odstępem. Zmienne logiczne, które mogą pojawiać się w formule to x1x2,..., xn. Formuła składa się z m klauzul, opisanych w kolejnych m wierszach, po jednej w wierszu. Każdy z tych wierszy zawiera liczby całkowite pooddzielane pojedynczymi odstępami. Pierwsza z tych liczb, l, 1 ≤ l ≤ n, to liczba literałów tworzących klauzulę. Dalej w wierszu znajduje się l liczb całkowitych reprezentujących kolejne literały klauzuli. Są to liczby różne od zera, z zakresu od - n do n. Liczba i (dla 1 ≤ i ≤ n) reprezentuje xi, a liczba - i reprezentuje ¬xi.

출력

Wypisuje dokładnie jeden wiersz wyjścia, zawierający przybliżoną prawdziwość formuły podanej w k-tym zestawie danych. Prawdziwość powinna być wypisana w postaci ułamka dziesiętnego, obliczonego ze względną dokładnością 3%. To znaczy, jeśli prawdziwość formuły to p, a jej obliczone przybliżenie to p', to musi zachodzić |p' - p| ≤ 0.03p.

예제 입력 1

0

예제 출력 1

0.5