불편을 끼쳐 드려 죄송합니다

크라쿠프의 야기엘론스키 대학교에서 공부하는 데는 장점과 단점이 있습니다. 장점은 야기엘론스키 대학교가 있다는 것입니다. 단점은 크라쿠프입니다. 더 정확히 말하면, 트램 선로 공사에 계속 시달려야 한다는 점입니다. 처음에 대중교통망에는 여러 개의 트램 노선이 있습니다. 그 뒤 노선 하나가 운행 중지되고, 다시 다른 노선이 중지되며, 이런 식으로 이어집니다. 크라쿠프에는 철칙이 있습니다. 이미 운행 중지된 노선이 운행을 재개하기 전에는, 반드시 다른 노선을 먼저 중지해야 합니다. 아직 중지되지 않은 노선도 남아 있습니다. 당신은 전차에 앉아 있고, 대학교로 가는 직통 노선이 방금 사라져 짜증이 납니다. 창밖을 보며 생각합니다. 나는 이 도시에서 가장 운이 나쁜 승객일까? 아니면 목적지에 가려고 환승을 더 많이 해야 하는 사람이 어딘가에 있을까? 더 정확히 말하면, 노선 $l_0, \ldots, l_c$가 존재하여 $l_0$이 정거장 $A$에 서고, $l_c$가 정거장 $B$에 서며, 모든 $0 \leq i < c$에 대해 $l_i$와 $l_{i+1}$이 모두 서는 정거장이 있을 때, 정거장 $B$는 정거장 $A$에서 $c$번 환승으로 도달할 수 있습니다. 각 시점마다, 정거장 쌍 $(A, B)$ 중에서 $B$가 $A$에서 $c$번 환승으로 도달 가능하면서, 어떤 $c' < c$번 환승으로도 도달할 수 없는 경우의 $c$ 최댓값을 구합니다. 정거장 쌍에 따라서는 아예 오갈 수 없을 수도 있습니다. 위 정의에 따라 이런 쌍은 분석에서 제외합니다. 그런 정거장 사이를 이동하려는 사람은 어차피 우버를 탈 것이라고 봅니다.

첫 줄에 테스트 케이스의 개수 $z$ ($1 \leq z \leq 35$)가 주어집니다. 각 테스트 케이스의 첫 줄에는 정거장 수 $n$과 노선 수 $k$가 주어집니다 ($2 \leq n, k \leq 750$). 정거장은 1부터 $n$까지, 노선은 1부터 $k$까지 번호가 매겨져 있습니다. 이어서 $k$개의 줄이 주어집니다. $i$번째 줄은 $i$번 노선의 경로를 나타냅니다. 각 줄은 $r_i$ ($2 \leq r_i \leq n$)로 시작하고, 이어서 노선이 서는 서로 다른 정거장 번호 $r_i$개 $a_{i,j}$ ($1 \leq a_{i,j} \leq n$)가 주어집니다. 모든 트램 노선은 양방향으로 운행합니다. 다음 줄에는 운행 중지된 노선의 수 $s$ ($1 \leq s \leq k-1$)가 주어집니다. 이어서 $s$개의 줄에 노선이 운행 중지되는 순서대로 노선 번호 $s_i$ ($1 \leq s_i \leq k$)가 주어집니다. 한 노선은 최대 한 번만 운행 중지됩니다. 모든 테스트 케이스에서 $n$의 합과 $k$의 합은 각각 1000을 넘지 않습니다.

각 테스트 케이스마다 $s+1$개의 줄을 출력합니다. 각 줄에는 정수 하나를 출력합니다. $i+1$번째 줄에는 $i$번째 운행 중지 이후 필요한 최대 환승 횟수를 출력합니다. 첫 줄에는 운행 중지가 없을 때의 답을 출력합니다.

처음에는 예를 들어 정거장 4에서 5로 (또는 그 반대로) 이동할 때 환승이 한 번 필요합니다. 노선 2를 타고 노선 1로 갈아타면 이동할 수 있습니다. 환승이 두 번 이상 필요한 정거장 쌍은 없습니다. 노선 1이 제거되면 정거장 1에서 3으로 (또는 그 반대로) 이동하는 데 환승이 두 번 필요합니다. 노선 1과 4가 제거되면 서로 도달할 수 있는 정거장 쌍은 (1, 4)와 (2, 3)뿐이며, 두 경우 모두 환승이 필요하지 않습니다. 노선 1, 4, 3이 제거되면 서로 도달할 수 있는 정거장 쌍은 (1, 4) 하나뿐입니다. 이 정거장들 사이에는 환승이 필요하지 않습니다.