G. Amoeba Tree
time limit per test
3 с
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a tree with $$$N$$$ vertices. On this tree, there are $$$M$$$ amoebas, each occupying a subset of the vertices. Importantly, the vertices occupied by any given amoeba always form a connected subset.

The goal is to eliminate all the amoebas. This can be achieved by shooting at a vertex, killing any amoeba that has even just a portion of its body within that vertex. More explicitly, if an amoeba is spread across multiple vertices and one of those vertices is targeted, the entire amoeba, regardless of its size or the number of vertices it spans, will be eliminated. You need to determine the minimum amount of ammunition required to eliminate all the amoebas.

Figure 1. The first test from the sample.

Additionally, $$$Q$$$ events will occur. In each event, the scenario is re-evaluated under the assumption that an additional amoeba has appeared. The task is to determine the new minimum amount of ammunition needed.

Note that this new amoeba will be eliminated by the end of the event (i.e., each event is independent).

Input

The first line contains one integer $$$T$$$ ($$$1 \leq T \leq 10^3$$$), the number of test cases.

Then, for each test case:

  • The first line contains three space-separated integers $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$, $$$1 \leq M \leq 2 \cdot 10^5$$$, $$$0 \leq Q \leq 2 \cdot 10^5$$$).
  • Then, $$$N-1$$$ lines follow, describing the tree. Each line contains two space-separated integers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq N$$$), indicating an edge between vertex $$$x$$$ and vertex $$$y$$$.
  • Next, $$$M$$$ lines follow, describing the amoebas. Each line starts with an integer $$$k_i$$$ followed by $$$k_i$$$ space-separated integers $$$v_{i,1}, v_{i,2}, \ldots, v_{i,k_i}$$$ ($$$1 \leq k_i, v_{i,j} \leq N$$$), where the vertices $$$v_{i,1}, v_{i,2}, \ldots, v_{i,k_i}$$$ form a connected subset from the tree and are all distinct.
  • Finally, $$$Q$$$ lines follow, describing additional amoebas for each event. Each line starts with an integer $$$l_i$$$ followed by $$$l_i$$$ space-separated integers $$$u_{i,1}, u_{i,2}, \ldots, u_{i,l_i}$$$ ($$$1 \leq l_i, u_{i,j} \leq N$$$), where the vertices $$$u_{i,1}, u_{i,2}, \ldots, u_{i,l_i}$$$ form a connected subset from the tree and are all distinct.

It is guaranteed that:

  • The total sum of $$$N$$$ across all tests does not exceed $$$2 \cdot 10^5$$$.
  • The total sum of $$$M$$$ across all tests does not exceed $$$2 \cdot 10^5$$$.
  • The total sum of $$$Q$$$ across all tests does not exceed $$$2 \cdot 10^5$$$.
  • The total sum of $$$k_i$$$ across all tests does not exceed $$$2 \cdot 10^5$$$.
  • The total sum of $$$l_i$$$ across all tests does not exceed $$$2 \cdot 10^5$$$.
Output

For each test, print $$$Q+1$$$ lines. The answer before events, and after each event. Note that the first line should contain the answer before any events take place!

Example
Input
2
7 3 3
1 2
1 3
2 6
2 7
6 4
4 5
6 1 2 6 7 4 5
3 1 2 7
3 4 5 6
1 3
1 7
2 4 6
1 2 0
1 1
1 1
Output
2
3
2
2
1