Konspiracja

Limit pamięci: 128 MB

Wroga Bitocja napadła zdradziecko na Bajtocję i okupuje znaczną jej część. Król Bajtocji, Bajtazar, chce zorganizować na okupowanych terenach ruch oporu. Bajtazar rozpoczął od wytypowania osób, które utworzą strukturę organizacyjną ruchu oporu. Należy je podzielić na dwie grupy: konspiratorów, którzy będą prowadzić bezpośrednią działalność na terenie okupowanym, oraz grupę wsparcia, która będzie działać z terytorium wolnej Bajtocji.

Pojawił się jednak pewien problem - podział taki musi spełniać następujące warunki:

  • Każde dwie osoby z grupy wsparcia powinny się znać - zagwarantuje to, że będą stanowiły zwartą i zgraną grupę.
  • Konspiratorzy nie powinni się znać nawzajem.
  • Żadna z grup nie może być pusta, tzn. musi być przynajmniej jeden konspirator i jedna osoba w grupie wsparcia.
Bajtazar zastanawia się, ile jest różnych sposobów podziału wytypowanych osób na dwie grupy zgodnie z powyższymi warunkami, a przede wszystkim, czy taki podział jest w ogóle możliwy. Jako że sam nie całkiem umie sobie z tym poradzić, poprosił Cię o pomoc.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę osób zaangażowanych w organizację ruchu oporu. Osoby te są ponumerowane od 1 do . W kolejnych wierszach opisane jest, które osoby się znają. W -tym z tych wierszy znajduje się opis znajomych osoby nr , złożony z liczb całkowitych pooddzielanych pojedynczymi odstępami. Pierwsza z tych liczb, (), oznacza liczbę znajomych osoby nr . Dalej w wierszu znajduje się liczb całkowitych . Liczby spełniają , oraz są podane w kolejności rosnącej. Możesz założyć, że jeśli w ciągu liczb występuje liczba , to także w ciągu liczb występuje liczba .

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą: liczbę sposobów, na które osoby mające utworzyć ruch oporu mogą zostać podzielone na grupę wsparcia i grupę działającą na terenach okupowanych. Jeżeli nie istnieje żaden podział wytypowanych osób na dwie grupy spełniający podane warunki, wówczas poprawnym wynikiem jest 0.

Przykład

Dla danych wejściowych:

4
2 2 3
2 1 3
3 1 2 4
1 3

poprawną odpowiedzią jest:

3

Wyjaśnienie do przykładu: Dla tej grupy spiskowców są możliwe trzy podziały na grupy. Grupę konspiratorów mogą stanowić uczestnicy o numerach i , o numerach i lub sam uczestnik o numerze .

Autor zadania: Jakub Onufry Wojtaszczyk.