We apologize for any inconvenience#11109
Studying at the Jagiellonian University in Krakow has its pros and cons. Pros: Jagiellonian University. Cons: Krakow... Or, more precisely, a constant necessity to deal with tram track reconstructions.
Initially, the public transport network consists of some number of tram lines. Then one of them gets suspended, then another one, and then another... As you may know yourself, the inviolable rule in Krakow is to always suspend a line before any of the previously suspended lines resumes its operation. Right now not all of the lines have been suspended (yet), and you sit in a tram, annoyed that your direct connection to the university has just disappeared. You look out of the window and you ask yourself: "Am I actually the most unlucky passenger in this city? Or is there someone out there somewhere who needs to change lines even more times in order to get where they want?"
More precisely, we say that stop is reachable from stop with changes if there exist lines l_0, \ldots, l_c such that l_0 serves stop , l_c serves stop , and for each 0 \le i < c there exists some stop served by l_i and l_{i+1}. At each point in time, you want to know the largest value of such that there exists a pair of stops (, ) where is reachable from with changes and is not reachable from with c' changes for any c' < c.
Note that sometimes it might not be possible to travel between a pair of stops at all. As follows from the definition above, you decide not to take such pairs into consideration in your analysis - you conclude that if someone wishes to travel between those stops, they will take an Uber anyway.
The first line contains the number of test cases (1 \le z \le 35). The descriptions of the test cases follow.
The first line of each test case contains the number of stops and the number of tram lines (2 \le n, k \le 750).
The stops are numbered from to and the lines are numbered from to .
Then lines follow. The -th of those lines describes the route of the tram line number . Each line starts with an integer r_i (2 \le r_i \le n) followed by r_i distinct integers a_{i,j} (1 \le a_{i,j} \le n) - the identifiers of stops served by the -th tram line. Any tram line runs in both directions.
The next line contains a single integer (1 \le s \le k - 1).
Then lines follow, describing the order in which the tram lines get suspended. Each of those lines contains a single integer s_i (1 \le s_i \le k) - the identifier of the suspended tram line. Any line can get suspended at most once.
The sums of values of and in all test cases do not exceed each.
For each test case, output s + 1 lines, each containing a single integer. The i + 1-th line should denote the largest number of line changes necessary after the -th suspension event (the first line denoting the answer before any suspensions).
Exemple 1
Initially, one line change is required to travel, for example, from stop to stop (or vice versa). Such travel is possible by taking line , then line . There are no pairs of stops requiring or more changes.
After line gets removed, two line changes are required to travel from stop to stop (or vice versa).
When lines and get removed, the only pairs of stops still reachable one from another are (, ) and (, ) and in both cases no line changes are required to travel between them.
When lines , and get removed, the only pair of stops still reachable one from another is (, ). No line changes are required to travel between these stops.