Studiowanie na Uniwersytecie Jagiellońskim w Krakowie ma swoje plusy i minusy. Plusy: Uniwersytet Jagielloński. Minusy: Kraków... A dokładniej, ciągła konieczność radzenia sobie z remontami torowisk tramwajowych.

Początkowo sieć transportu publicznego składa się z pewnej liczby linii tramwajowych. Następnie jedna z nich zostaje zawieszona, potem kolejna, i jeszcze kolejna... Jak zapewne wiesz, nienaruszalną zasadą w Krakowie jest zawsze zawieszenie linii przed wznowieniem działania którejkolwiek z wcześniej zawieszonych. Obecnie nie wszystkie linie zostały (jeszcze) zawieszone, a Ty siedzisz w tramwaju, zirytowany, że Twoje bezpośrednie połączenie z uniwersytetem właśnie zniknęło. Wyglądasz przez okno i zadajesz sobie pytanie: „Czy jestem najbardziej pechowym pasażerem w tym mieście? A może jest gdzieś ktoś, kto musi przesiadać się jeszcze więcej razy, aby dotrzeć tam, gdzie chce?”.

Mówiąc dokładniej, powiemy, że przystanek $B$ jest osiągalny z przystanku $A$ przy $c$ przesiadkach, jeśli istnieją linie $l_0, \dots, l_c$ takie, że $l_0$ obsługuje przystanek $A$, $l_c$ obsługuje przystanek $B$, oraz dla każdego $0 \le i < c$ istnieje przystanek obsługiwany zarówno przez $l_i$, jak i $l_{i+1}$. W każdym momencie chcesz poznać największą wartość $c$, dla której istnieje para przystanków $(A, B)$, gdzie $B$ jest osiągalny z $A$ przy $c$ przesiadkach, a $B$ nie jest osiągalny z $A$ przy $c'$ przesiadkach dla żadnego $c' < c$.

Zauważ, że czasami podróż między parą przystanków może być w ogóle niemożliwa. Zgodnie z powyższą definicją, decydujesz się nie brać takich par pod uwagę w swojej analizie – uznajesz, że jeśli ktoś chce podróżować między takimi przystankami, i tak pojedzie Uberem.

Wejście

Pierwsza linia wejścia zawiera liczbę przypadków testowych $z$ ($1 \le z \le 35$). Następnie następują opisy przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera liczbę przystanków $n$ oraz liczbę linii tramwajowych $k$ ($2 \le n, k \le 750$). Przystanki są ponumerowane od $1$ do $n$, a linie od $1$ do $k$.

Następnie następuje $k$ linii. $i$-ta z tych linii opisuje trasę linii tramwajowej numer $i$. Każda linia zaczyna się od liczby całkowitej $r_i$ ($2 \le r_i \le n$), po której następuje $r_i$ różnych liczb całkowitych $a_{i,j}$ ($1 \le a_{i,j} \le n$) – identyfikatorów przystanków obsługiwanych przez $i$-tą linię tramwajową. Każda linia tramwajowa kursuje w obu kierunkach.

Kolejna linia zawiera pojedynczą liczbę całkowitą $s$ ($1 \le s \le k - 1$).

Następnie następuje $s$ linii opisujących kolejność zawieszania linii tramwajowych. Każda z tych linii zawiera pojedynczą liczbę całkowitą $s_i$ ($1 \le s_i \le k$) – identyfikator zawieszanej linii tramwajowej. Każda linia może zostać zawieszona co najwyżej raz.

Suma wartości $n$ oraz $k$ we wszystkich przypadkach testowych nie przekracza $1000$ dla każdego z nich.

Wyjście

Dla każdego przypadku testowego wypisz $s + 1$ linii, z których każda zawiera pojedynczą liczbę całkowitą. $(i+1)$-sza linia powinna oznaczać największą liczbę przesiadek koniecznych po $i$-tym zdarzeniu zawieszenia (pierwsza linia oznacza odpowiedź przed jakimikolwiek zawieszeniami).

Przykład

Wejście 1

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

Wyjście 1

1
2
0
0

Uwagi

Początkowo wymagana jest jedna przesiadka, aby podróżować, na przykład, z przystanku 4 do przystanku 5 (lub odwrotnie). Taka podróż jest możliwa dzięki skorzystaniu z linii 2, a następnie linii 1. Nie ma par przystanków wymagających 2 lub więcej przesiadek.

Po usunięciu linii 1, wymagane są dwie przesiadki, aby podróżować z przystanku 1 do przystanku 3 (lub odwrotnie).

Kiedy linie 1 i 4 zostaną usunięte, jedynymi parami przystanków, które nadal są osiągalne jeden z drugiego, są (1, 4) oraz (2, 3), i w obu przypadkach nie są wymagane żadne przesiadki, aby podróżować między nimi.

Kiedy linie 1, 4 i 3 zostaną usunięte, jedyną parą przystanków, która nadal jest osiągalna jeden z drugiego, jest (1, 4). Nie są wymagane żadne przesiadki, aby podróżować między tymi przystankami.