Étudier à l'Université Jagellonne de Cracovie a ses avantages et ses inconvénients. Avantages : l'Université Jagellonne. Inconvénients : Cracovie... Ou, plus précisément, une nécessité constante de faire face aux reconstructions des voies de tramway.

Initialement, le réseau de transport public se compose d'un certain nombre de lignes de tramway. Puis l'une d'entre elles est suspendue, puis une autre, et encore une autre... Comme vous le savez peut-être, la règle inviolable à Cracovie est de toujours suspendre une ligne avant que l'une des lignes précédemment suspendues ne reprenne son service. À l'heure actuelle, toutes les lignes n'ont pas (encore) été suspendues, et vous êtes assis dans un tramway, agacé que votre connexion directe vers l'université vienne de disparaître. Vous regardez par la fenêtre et vous vous demandez : « Suis-je vraiment le passager le plus malchanceux de cette ville ? Ou y a-t-il quelqu'un, quelque part, qui a besoin de changer de ligne encore plus de fois pour arriver là où il veut ? »

Plus précisément, nous disons qu'un arrêt $B$ est accessible depuis un arrêt $A$ avec $c$ changements s'il existe des lignes $l_0, \dots, l_c$ telles que $l_0$ dessert l'arrêt $A$, $l_c$ dessert l'arrêt $B$, et pour chaque $0 \le i < c$, il existe un arrêt desservi à la fois par $l_i$ et $l_{i+1}$. À chaque instant, vous voulez connaître la plus grande valeur de $c$ telle qu'il existe une paire d'arrêts $(A, B)$ où $B$ est accessible depuis $A$ avec $c$ changements et $B$ n'est pas accessible depuis $A$ avec $c'$ changements pour tout $c' < c$.

Remarquez que parfois, il peut être impossible de voyager entre une paire d'arrêts. Comme le suggère la définition ci-dessus, vous décidez de ne pas prendre en considération de telles paires dans votre analyse – vous concluez que si quelqu'un souhaite voyager entre ces arrêts, il prendra un Uber de toute façon.

Entrée

La première ligne de l'entrée contient le nombre de cas de test $z$ ($1 \le z \le 35$). Les descriptions des cas de test suivent.

La première ligne de chaque cas de test contient le nombre d'arrêts $n$ et le nombre de lignes de tramway $k$ ($2 \le n, k \le 750$). Les arrêts sont numérotés de $1$ à $n$ et les lignes sont numérotées de $1$ à $k$.

Ensuite, $k$ lignes suivent. La $i$-ième de ces lignes décrit l'itinéraire de la ligne de tramway numéro $i$. Chaque ligne commence par un entier $r_i$ ($2 \le r_i \le n$) suivi de $r_i$ entiers distincts $a_{i,j}$ ($1 \le a_{i,j} \le n$) – les identifiants des arrêts desservis par la $i$-ième ligne de tramway. Toute ligne de tramway circule dans les deux sens.

La ligne suivante contient un entier unique $s$ ($1 \le s \le k - 1$).

Ensuite, $s$ lignes suivent, décrivant l'ordre dans lequel les lignes de tramway sont suspendues. Chacune de ces lignes contient un entier unique $s_i$ ($1 \le s_i \le k$) – l'identifiant de la ligne de tramway suspendue. Toute ligne peut être suspendue au plus une fois.

La somme des valeurs de $n$ et $k$ dans tous les cas de test ne dépasse pas 1000 chacun.

Sortie

Pour chaque cas de test, affichez $s + 1$ lignes, chacune contenant un entier unique. La $(i+1)$-ième ligne doit indiquer le plus grand nombre de changements de ligne nécessaires après le $i$-ième événement de suspension (la première ligne indiquant la réponse avant toute suspension).

Exemples

Entrée 1

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

Sortie 1

1
2
0
0

Remarque

Initialement, un changement de ligne est nécessaire pour voyager, par exemple, de l'arrêt 4 à l'arrêt 5 (ou vice versa). Un tel voyage est possible en prenant la ligne 2, puis la ligne 1. Il n'y a aucune paire d'arrêts nécessitant 2 changements ou plus.

Après la suppression de la ligne 1, deux changements de ligne sont nécessaires pour voyager de l'arrêt 1 à l'arrêt 3 (ou vice versa).

Lorsque les lignes 1 et 4 sont supprimées, les seules paires d'arrêts encore accessibles l'une de l'autre sont (1, 4) et (2, 3), et dans les deux cas, aucun changement de ligne n'est nécessaire pour voyager entre eux.

Lorsque les lignes 1, 4 et 3 sont supprimées, la seule paire d'arrêts encore accessible l'une de l'autre est (1, 4). Aucun changement de ligne n'est nécessaire pour voyager entre ces arrêts.