HH Country

HH is the strongest country in competitive programming. It has $n$ cities numbered 1 to $n$, and the cities are connected by roads. Between any two different cities there is exactly one path, so the cities and roads of HH form a tree.

HH runs a contest to split the budget of the Forward-looking Infrastructure Development Program. The contest has $m$ rounds, and round $i$ decides how budget $i$ is distributed. The distribution follows the result of a double round robin among the $k_i$ cities attached to that budget. For two different participating cities A and B, one game is played with A travelling to B, and one game is played with B travelling to A. A round therefore holds $k_i \times (k_i - 1)$ games in total.

To itemize the travel expenses, HH needs the total travelling distance between the participating cities of each round. The distance of one game is the number of roads on the only path from the away city to the home city. For every round, compute the sum of that distance over all games of the round.

The first line contains an integer $T$, the number of test cases.

The first line of each test case contains two integers $n$ and $m$, the number of cities and the number of rounds. Each of the next $n - 1$ lines contains two integers $u$ and $v$, meaning there is a road between city $u$ and city $v$. Each of the next $m$ lines begins with an integer $k_i$, the number of cities taking part in round $i$, followed on the same line by the labels $c_{i,1}, c_{i,2}, \dots, c_{i,k_i}$ of those cities.

• $1 \le T \le 100$
• $2 \le n \le 10^5$
• $1 \le m \le 10^5$
• $1 \le u, v, c_{i,j} \le n$
• $2 \le k_i \le n$
• All $c_{i,j}$ in one round are distinct.
• $\sum_i k_i \le 2 \times 10^5$ within one test case.
• The input file is not larger than 60MB.

For each round, print the total travelling distance of that round on its own line, in the order the rounds are given.