M. Giant Worms
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Joãozinho is an astronomer who has just started his master's degree at UFMG, studying the "worms" of the multiverse.

The multiverse is the set of all universes that exist, and Joãozinho is researching a hierarchical way to represent it. In his studies, each universe in the multiverse is assigned an integer $$$u$$$ as its identifier, and in each universe, there are several giant worms that allow travel to other universes.

The first thing Joãozinho did was to write down all the facts he knows about the multiverse. Here is everything he recorded:

  • If a universe $$$u$$$ has a giant worm that allows travel to universe $$$v$$$, then it is physically impossible for universe $$$v$$$ to have a worm that allows travel back to universe $$$u$$$.
  • The multiverse can be modeled as a directed tree, where the nodes of the tree are universes and an edge from universe $$$u$$$ to $$$v$$$ represents a giant worm that allows travel from $$$u$$$ to $$$v$$$.
  • There exists exactly one universe from which all other universes can be reached. Joãozinho labeled this universe with the number $$$1$$$.
  • If universe $$$u$$$ has a worm that allows travel to universe $$$v$$$, then the number of stars in universe $$$u$$$ is strictly greater than the number of stars in universe $$$v$$$.

Joãozinho's master's advisor, Karina, gave him a task to simulate any multiverse that obeys the rules of the real multiverse, and this simulation must be able to answer very specific questions about any multiverse.

After weeks of hard work, Joãozinho is almost done, but one "sub-task" remains, and he can't solve it. It is defined as follows:

Given $$$K$$$ universes $$$a_1, a_2, \cdots, a_K$$$, calculate the following sum:

Where $$$f(i, j)$$$ is the number representing the universe with the smallest number of stars from which it is possible to travel to universes $$$a_i, a_{i + 1}, \cdots, a_{j - 1}, a_j$$$.

Joãozinho is out of ideas on how to solve this, so he asked for your help to write a program that receives $$$Q$$$ such queries and answers them.

Input

The first line of input contains two integers $$$N$$$ $$$(1 \le N \le 10^5)$$$ and $$$Q$$$ $$$(1 \le Q \le 10^5)$$$, the number of universes in the simulated multiverse and the number of queries, respectively.

The next $$$N - 1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le N)$$$, indicating that there is a giant worm in universe $$$u$$$ that allows travel to universe $$$v$$$.

It is guaranteed that the given multiverse satisfies all the facts and conventions Joãozinho recorded.

The next $$$Q$$$ lines each contain an integer $$$K$$$ $$$(1 \le K \le N)$$$, followed by $$$K$$$ integers $$$a_1, \cdots , a_K$$$, the universes in the query. It is guaranteed that all universes in a query are distinct, and also the sum of $$$K$$$ over all queries does not exceed $$$3 \cdot 10^5$$$.

Output

The output must consist of $$$Q$$$ lines, each containing a single integer — the answer to the corresponding query.

Examples
Input
5 2
1 2
1 3
3 4
3 5
1 2
2 4 5
Output
2
12
Input
4 1
1 2
1 3
1 4
3 2 3 4
Output
12
Input
1 1
1 1
Output
1
Note

Explanation for the first example:

In the first query, only one universe is given, so the universe with the fewest stars that can reach universe $$$2$$$ is universe $$$2$$$ itself. In the second query, the answer is $$$f(1, 1) + f(1, 2) + f(2, 2) = 4 + 3 + 5 = 12$$$.