III Mistrzostwa Wielkopolski w Programowaniu Zespołowym 2-3 grudnia 2005
Zadanie G. Kryształ

Opis

Naukowcy ostatnio odkryli, że bryła uranu, pod wpływem pewnych czynników temperaturowo-ciśnieniowych oraz promieniowania elektromagnetycznego staje się kryształem o świetnych właściwościach do produkcji broni atomowej. Taki kryształ złożony jest z atomów uranu, które parami wzajemnie ze sobą oddziałują w pewien specyficzny sposób, o którym opowiemy za chwilę. Oddziaływanie dwóch atomów polega na wymienianiu się ze sobą elektronami. Atom może niezależnie oddziaływać z kilkoma innymi atomami, nawet z większą liczbą atomów niż ma elektronów. Co ciekawe, atom może wymieniać się elektronami z odległymi od siebie atomami, podczas gdy wcale nie musi wymieniać się z bliskimi.

Nauka ostatnimi laty poszła tak do przodu, że naukowcy są w stanie bardzo dokładnie zbadać, które atomy, z którymi oddziałują, analizując zmienność natężenia pola elektromagnetycznego między nimi. Dzięki temu mogą swobodnie zająć się badaniem własności wspomnianych już specyficznych oddziaływań. Odkryto, że własności bojowe kryształu związane są z tzw. „czworokątami”. Czworokąt to inaczej cztery atomy, których wzajemne oddziaływania tworzą cykl (np. atomy ABC i D tworzą taki cykl gdy A oddziałuje z B, B z C, C z DD z A). Wyróżniamy trzy rodzaje czworokątów: czysty, zanieczyszczony oraz brudny. Czworokąt czysty nie posiada przekątnych (kontynuując w/w przykład: A nie oddziałuje z C, ani B z D), zanieczyszczony posiada dokładnie jedną przekątną (albo A oddziaływuje z C, albo B z D), a brudny ma obie przekątne (A oddziaływuje z CB z D). Najbardziej wartościowe są czworokąty czyste. Czworokąty zanieczyszczone również są wartościowe, ale już nie tak bardzo. Z kolei brudne w ogóle nie przejawiają żadnych interesujących właściwości. Wartość całego kryształu to suma liczby czworokątów zanieczyszczonych oraz podwojonej liczby czworokątów czystych. Uwaga! Jeden atom może znajdować się w kilku różnych czworokątach.

W procesie produkcji kryształów każdy z nich wychodzi trochę inaczej. Analiza ręczna przy masowej produkcji jest niewykonalna, więc naukowcy chcą zautomatyzować proces analizy jakości kryształów. Poprosili Cię byś napisał program, który obliczy wartość kryształu, na podstawie wykrytych oddziaływań między jego atomami.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych, z których każdy opisuje jeden kryształ do zbadania. W pierwszej linii każdego zestawu będzie liczba całkowita N (1 ≤ N ≤ 200), oznaczająca liczbę atomów kryształu. W kolejnych N liniach znajdują się opisy oddziaływań. W i-tej linii (1 ≤ i ≤ N) wymienione są atomy, z którymi oddziałuje i-ty atom. Lista poprzedzona jest liczbą całkowitą ki (0 ≤ ki ≤ N-1) oznaczającą jej długość, po której następuje ki różnych liczb całkowitych (z przedziału od 1 do N, różnych od i), będących numerami atomów. z którymi oddziałuje i-ty atom. Oczywiście jeśli atom A oddziałuje z B, to B oddziałuje też z A, więc nie zawsze ta informacja musi być podana na wejściu podwójnie.

Specyfikacja wyjścia

Dla każdego zestawu danych wypisz jedną liczbę całkowitą - wartość kryształu.

Przykład

Wejście

3
4
1 2
1 3
1 4
1 1
4
1 3
1 4
2 2 4
1 1
6
2 2 3
3 6 5 3
3 6 4 2
1 5
0
2 2 3

Wyjście

2
1
3