Problem E: Biała myszka

Treść

Na lekcjach biologii u pani Asi nigdy nie jest nudno. Uczniowie nie wkuwają dziwnych i niezrozumiałych nazw gatunków. Pani biolog stara się jak najwięcej wiedzy przekazać przez obcowanie z żywą naturą. Często zabiera dzieci na wycieczki do lasu, ogrodu botanicznego czy do zoo, przynosi na lekcje ciekawe egzemplarze roślin. Sala biologiczna sama w sobie przypomina mały zwierzyniec. Są tam dwie papużki, które trajkoczą jak polonistka z bibliotekarką, wielka świnka morska, która nie wiedzieć czemu wszystkim przypomina pana dyrektora i jaszczurka, która akurat do nikogo nie jest podobna. Czasem zdarza się, że któryś z uczniów przyniesie na lekcję małego gryzonia, gada, czy innego pupila. Wtedy opowiada całej klasie o jego zwyczajach, diecie i harcach, które zwierzak wyczynia w domu.

Podobnie było i tym razem. Kazio chciał się koniecznie pochwalić swoją tresowaną białą myszką. Na lekcje pani Asi przyniósł więc niezbędne akcesoria: zbudowany przez siebie labirynt i kilka kawałków sera. Labirynt był tak wykonany, że miał tylko jedno wejście i jedno wyjście. Wszystkie jego korytarze położone były na tej samej wysokości, nie przecinały się, a ponadto były skonstruowane w ten sposób, że myszka mogła poruszać się tylko w jednym, wyznaczonym kierunku. Prowadziły zawsze do przodu, zbaczając czasem w lewo lub w prawo. Korytarze łączyły się w pokoikach, przy czym dowolne dwa pokoiki były bezpośrednio połączone co najwyżej jednym korytarzem. Z każdego pokoiku można było dojść do końca labiryntu, a z początku labiryntu można było dojść do każdego pokoiku. Kazio układał we wszystkich korytarzach i pokoikach po kawałku sera i wpuszczał myszkę na początek. Biały gryzoń poruszał się w kierunkach wyznaczonych przez korytarze zjadając po drodze kawałki sera i kończąc wędrówkę na wyjściu labiryntu. I nie byłoby w tym nic nadzwyczajnego gdyby nie fakt, iż tak dobierał sobie trasę by zjeść cały ser w jak najmniejszej liczbie wędrówek z początku na koniec labiryntu.

Cała klasa zaintrygowana tym faktem postanowiła wybudować różnego rodzaju labirynty, zachowując zasady konstrukcji zgodne z pierwowzorem i przekonać się, czy myszka Kazia poradzi sobie z nowymi zadaniami. Aby móc stwierdzić czy zwierzątko rzeczywiście wybiera optymalne trasy trzeba najpierw takie wyznaczyć. I tu jest pole do popisu dla Ciebie. Napisz program, który dla podanego opisu labiryntu obliczy minimalną liczbę wędrówek potrzebnych na zjedzenie wszystkich kawałków sera.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera liczbę całkowitą n (2<=n<=20 000) pokoików w labiryncie, przy czym wejście symbolizuje pokoik numer 1, a wyjście pokoik numer n. W kolejnych n−1 wierszach podane są opisy korytarzy wychodzących z kolejnych pokoików, w wierszu drugim zawarty jest opis pokoiku nr 1, w trzecim pokoiku nr 2, itd. Opis korytarzy składa się z ciągu liczb całkowitych oddzielonych pojedynczymi spacjami. Pierwsza liczba, p_i (1<=p_i<n), oznacza liczbę korytarzy wychodzących z i-tego pokoiku. Dalej znajduje się p_i liczb k_i,j (2<=k_i,j<=n) opisujących numery pokoików, do których prowadzą kolejne korytarze. Korytarze są uporządkowane względem kierunku lewo – prawo. Pierwszy jest podany ten idący najbardziej w lewo i dalej kolejno w kierunku na prawo.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest liczba całkowita – minimalna liczba wędrówek białej myszki potrzebnych do zjedzenia wszystkich kawałków sera.

Przykład

dane wejściowe:
1
7
3 3 4 6
1 7
1 7
1 3
1 7
2 2 5

wynik:
4