Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KEYS - Klucze

W Megabajtolandii właściciele banków mocno dbają o bezpieczeństwo. Starają się by jeden pracownik nie trzymał kluczy do wszystkich sejfów, gdyż wystarczyłoby tylko jego przekupić lub napaść, żeby mieć dostęp do całej zawartości banku. Początkowo wprowadzono taki system, że za każdy sejf był odpowiedzialny dokładnie jeden pracownik i tylko on miał do niego klucz (i do żadnego innego). Ten system jednak się również nie sprawdził, gdyż nieobecność pracownika uniemożliwiała otwarcie “jego” sejfu. Wprowadzono więc w końcu rozwiązanie kompromisowe. Jak w poprzednim rozwiązaniu każdy pracownik opiekuje się swoim sejfem, ale tym razem w sejfach oprócz pieniędzy mogą znajdować się także klucze do innych sejfów. Dzięki temu nie potrzeba wszystkich pracowników, żeby móc otworzyć każdy sejf.

Ten system może i nawet byłby dobry, ale niestety obecnie klucze do sejfów przydzielane są dość bezładnie. Zdarza się tak, że w sejfie leżą klucze do samego siebie, albo kilka kluczy do tego samego sejfu. Co gorsza, w niektórych bankach dochodzi do takiej sytuacji, że jeden pracownik jest mimo wszystko w stanie otworzyć wszystkie sejfy (czyli wracamy do punktu wyjścia). Szefowie banków zarządzili więc generalną inspekcję w swoich bankach. Chcą wiedzieć jak bardzo ich sejfy są bezpieczne. Konkretnie interesuje ich to, jak dużo pracowników złodzieje musieliby przekupić/napaść, żeby mieć dostęp do wszystkich sejfów.

Zadanie

Dla podanej liczby sejfów oraz rozkładu kluczy w nich Twój program powinien określić ile najmniej pracowników potrzeba do otwarcia wszystkich sejfów.

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita, oznaczająca liczbę banków w Megabajtolandii, które wprowadziły powyższy system. Opis każdego z banków jest następujący. W pierwszej linii znajduje się jedna liczba całkowita N (1 ≤ N ≤ 10.000), oznaczająca liczbę sejfów (a tym samym liczbę pracowników trzymających klucze do nich). Wiersze od 2 do N+1 opisu banku przedstawiają zawartość kolejnych sejfów (wiersz i+1 zawiera opis sejfu o numerze i, gdzie 1 ≤ iN). Wiersz z zawartością sejfu zaczyna się od nieujemnej liczby całkowitej M, mówiącej ile kluczy jest w danym sejfie, po której następuje M liczb całkowitych z zakresu od 1 do N - są to numery sejfów, do których klucze znajdują się w danym sejfie. Można przyjąć, że w żadnym banku łączna liczba kluczy we wszystkich sejfach nie przekracza 100.000.

Specyfikacja wyjścia

Dla każdego banku opisanego na wejściu należy wypisać dokładnie jedną liczbę całkowitą (każdą w osobnej linii), oznaczającą minimalną liczbę pracowników niezbędna do otwarcia wszystkich sejfów.

Przykład

Wejście

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

Wyjście

1
3

Dodane przez:adrian
Data dodania:2005-11-26
Limit czasu wykonania programu:0.100s-0.250s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:MWPZ 2003

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.