크라쿠프의 야기엘로니안 대학교에서 공부하는 것에는 장단점이 있습니다. 장점: 야기엘로니안 대학교. 단점: 크라쿠프... 더 정확히 말하자면, 끊임없이 발생하는 트램 선로 재건 공사에 대처해야 한다는 점입니다.

처음에 대중교통 네트워크는 여러 개의 트램 노선으로 구성되어 있습니다. 그러다 하나가 운행 중단되고, 또 다른 하나가 중단되고, 계속해서 중단됩니다... 여러분도 아시다시피 크라쿠프의 철칙은 이전에 중단된 노선이 운행을 재개하기 전에 항상 새로운 노선을 먼저 중단시키는 것입니다. 현재 모든 노선이 중단된 것은 아니지만, 여러분은 트램에 앉아 대학으로 가는 직통 연결편이 방금 사라진 것에 짜증을 내고 있습니다. 창밖을 내다보며 스스로에게 묻습니다. "내가 정말 이 도시에서 가장 운 없는 승객인가? 아니면 어딘가에 목적지에 가기 위해 나보다 더 많이 노선을 갈아타야 하는 사람이 있는 걸까?"

더 정확히 말하자면, 정류장 $A$에서 정류장 $B$까지 $c$번의 환승으로 도달 가능하다는 것은, $l_0, \dots, l_c$ 노선이 존재하여 $l_0$가 정류장 $A$를 경유하고, $l_c$가 정류장 $B$를 경유하며, 모든 $0 \le i < c$에 대해 $l_i$와 $l_{i+1}$이 공통으로 경유하는 정류장이 존재함을 의미합니다. 매 순간, 여러분은 정류장 쌍 $(A, B)$ 중 $A$에서 $B$까지 $c$번의 환승으로 도달 가능하고, 임의의 $c' < c$에 대해서는 $A$에서 $B$까지 $c'$번의 환승으로 도달 불가능한 경우가 존재하는 가장 큰 $c$ 값을 알고 싶어 합니다.

때로는 정류장 쌍 사이를 전혀 이동할 수 없을 수도 있다는 점에 유의하십시오. 위의 정의에 따라, 그러한 쌍은 분석에서 고려하지 않기로 결정합니다. 즉, 누군가 그러한 정류장 사이를 이동하고 싶어 한다면 어차피 우버를 탈 것이라고 결론 내립니다.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 $z$ ($1 \le z \le 35$)가 포함됩니다. 각 테스트 케이스에 대한 설명이 이어집니다.

각 테스트 케이스의 첫 번째 줄에는 정류장의 수 $n$과 트램 노선의 수 $k$ ($2 \le n, k \le 750$)가 포함됩니다. 정류장은 $1$부터 $n$까지 번호가 매겨져 있고, 노선은 $1$부터 $k$까지 번호가 매겨져 있습니다.

그다음 $k$개의 줄이 이어집니다. 이 중 $i$번째 줄은 트램 노선 번호 $i$의 경로를 설명합니다. 각 줄은 정수 $r_i$ ($2 \le r_i \le n$)로 시작하며, 이어서 $i$번째 트램 노선이 경유하는 정류장의 식별자인 $r_i$개의 서로 다른 정수 $a_{i,j}$ ($1 \le a_{i,j} \le n$)가 주어집니다. 모든 트램 노선은 양방향으로 운행합니다.

다음 줄에는 정수 $s$ ($1 \le s \le k - 1$)가 포함됩니다.

그다음 $s$개의 줄이 이어지며, 트램 노선이 중단되는 순서를 설명합니다. 각 줄에는 중단되는 트램 노선의 식별자인 정수 $s_i$ ($1 \le s_i \le k$)가 포함됩니다. 모든 노선은 최대 한 번만 중단될 수 있습니다.

모든 테스트 케이스에서 $n$과 $k$ 값의 합은 각각 $1000$을 넘지 않습니다.

출력

각 테스트 케이스에 대해 $s + 1$개의 줄을 출력하며, 각 줄에는 하나의 정수가 포함되어야 합니다. $i + 1$번째 줄은 $i$번째 중단 이벤트 이후에 필요한 최대 환승 횟수를 나타내야 합니다 (첫 번째 줄은 중단 전의 답을 나타냄).

예제

입력 1

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

출력 1

1
2
0
0

참고

처음에는 예를 들어 정류장 4에서 정류장 5로 이동하려면 (또는 그 반대도 마찬가지) 1번의 환승이 필요합니다. 이러한 이동은 노선 2를 탄 다음 노선 1을 타면 가능합니다. 2번 이상의 환승이 필요한 정류장 쌍은 없습니다.

노선 1이 제거된 후, 정류장 1에서 정류장 3으로 이동하려면 (또는 그 반대도 마찬가지) 2번의 환승이 필요합니다.

노선 1과 4가 제거되면, 서로 도달 가능한 정류장 쌍은 (1, 4)와 (2, 3)뿐이며, 두 경우 모두 이동하는 데 환승이 필요하지 않습니다.

노선 1, 4, 3이 제거되면, 서로 도달 가능한 정류장 쌍은 (1, 4)뿐입니다. 이 정류장들 사이를 이동하는 데 환승은 필요하지 않습니다.