Estudiar en la Universidad Jaguelónica de Cracovia tiene sus pros y sus contras. Pros: la Universidad Jaguelónica. Contras: Cracovia... O, más precisamente, la necesidad constante de lidiar con las reconstrucciones de las vías del tranvía.

Inicialmente, la red de transporte público consta de cierto número de líneas de tranvía. Luego, una de ellas es suspendida, después otra, y luego otra... Como quizás sepas, la regla inviolable en Cracovia es suspender siempre una línea antes de que cualquiera de las líneas suspendidas previamente reanude su operación. En este momento, no todas las líneas han sido suspendidas (todavía), y tú estás sentado en un tranvía, molesto porque tu conexión directa a la universidad acaba de desaparecer. Miras por la ventana y te preguntas: "¿Soy realmente el pasajero con más mala suerte de esta ciudad? ¿O hay alguien ahí fuera en algún lugar que necesite cambiar de línea aún más veces para llegar a donde quiere?"

Más precisamente, decimos que la parada $B$ es alcanzable desde la parada $A$ con $c$ cambios si existen líneas $l_0, \dots, l_c$ tales que $l_0$ sirve a la parada $A$, $l_c$ sirve a la parada $B$, y para cada $0 \le i < c$ existe alguna parada servida por $l_i$ y $l_{i+1}$. En cada momento, quieres conocer el valor más grande de $c$ tal que existe un par de paradas $(A, B)$ donde $B$ es alcanzable desde $A$ con $c$ cambios y $B$ no es alcanzable desde $A$ con $c'$ cambios para ningún $c' < c$.

Nota que a veces puede no ser posible viajar entre un par de paradas en absoluto. Como se desprende de la definición anterior, decides no tomar en cuenta tales pares en tu análisis; concluyes que si alguien desea viajar entre esas paradas, tomará un Uber de todos modos.

Entrada

La primera línea de la entrada contiene el número de casos de prueba $z$ ($1 \le z \le 35$). Siguen las descripciones de los casos de prueba.

La primera línea de cada caso de prueba contiene el número de paradas $n$ y el número de líneas de tranvía $k$ ($2 \le n, k \le 750$). Las paradas están numeradas del 1 al $n$ y las líneas están numeradas del 1 al $k$.

Luego, siguen $k$ líneas. La $i$-ésima de esas líneas describe la ruta de la línea de tranvía número $i$. Cada línea comienza con un entero $r_i$ ($2 \le r_i \le n$) seguido de $r_i$ enteros distintos $a_{i,j}$ ($1 \le a_{i,j} \le n$) — los identificadores de las paradas servidas por la $i$-ésima línea de tranvía. Cualquier línea de tranvía funciona en ambas direcciones.

La siguiente línea contiene un solo entero $s$ ($1 \le s \le k - 1$).

Luego, siguen $s$ líneas, describiendo el orden en el que las líneas de tranvía son suspendidas. Cada una de esas líneas contiene un solo entero $s_i$ ($1 \le s_i \le k$) — el identificador de la línea de tranvía suspendida. Cualquier línea puede ser suspendida como máximo una vez.

La suma de los valores de $n$ y $k$ en todos los casos de prueba no excede 1000 cada uno.

Salida

Para cada caso de prueba, imprime $s + 1$ líneas, cada una conteniendo un solo entero. La $(i+1)$-ésima línea debe denotar el mayor número de cambios de línea necesarios después del $i$-ésimo evento de suspensión (la primera línea denota la respuesta antes de cualquier suspensión).

Ejemplos

Entrada 1

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

Salida 1

1
2
0
0

Nota

Inicialmente, se requiere un cambio de línea para viajar, por ejemplo, de la parada 4 a la parada 5 (o viceversa). Dicho viaje es posible tomando la línea 2, luego la línea 1. No hay pares de paradas que requieran 2 o más cambios.

Después de que la línea 1 es eliminada, se requieren dos cambios de línea para viajar de la parada 1 a la parada 3 (o viceversa).

Cuando las líneas 1 y 4 son eliminadas, los únicos pares de paradas que siguen siendo alcanzables entre sí son (1, 4) y (2, 3), y en ambos casos no se requieren cambios de línea para viajar entre ellos.

Cuando las líneas 1, 4 y 3 son eliminadas, el único par de paradas que sigue siendo alcanzable entre sí es (1, 4). No se requieren cambios de línea para viajar entre estas paradas.