시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB61252447.059%

문제

Spring cleanings are probably the most boring parts of our lives, except this year, when Flóra and her mother found a dusty old tree graph under the carpet.

This tree has N nodes (numbered from 1 to N), connected by N − 1 edges. The edges gathered too much dust, so Flóra’s mom decided to clean them.

Cleaning the edges of an arbitrary tree is done by repeating the following process: She chooses 2 different leaves (a node is a leaf if it is connected to exactly one other node by an edge), and cleans every edge lying on the shortest path between them. If this path has d edges, then the cost of cleaning this path is d.

She doesn’t want to harm the leaves of the tree, so she chooses every one of them at most once. A tree is cleaned when all of its edges are cleaned. The cost of this is the sum of costs for all cleaned paths.

Flóra thinks the tree they found is too small and simple, so she imagines Q variations of it. In the i-th variation, she adds a total of Di extra leaves to the original tree: for each new leaf, she chooses a node from the original tree, and connects that node with the new leaf by an edge. Note that some nodes may stop being leaves during this step.

For all these Q variations, we are interested in the minimum cost that is required to clean the tree.

입력

The first line contains two space-separated integers, N and Q.

Each of the next N − 1 lines contains two space-separated integers u and v, denoting that nodes u and v are connected by an edge.

The next Q lines describe the variations: the first integer in the i-th line is Di. Then Di space-separated integers follow: if the j-th number is aj, it means that Flóra adds a new leaf to the node aj. We may add more than one leaf to the same node.

After each variation, Flóra restarts and adds extra leaves to the original tree.

출력

You should print Q lines. In the i-th line print a single integer: the minimum cost required to clean the i-th variation of the tree. If the tree cannot be cleaned, print −1.

제한

  • 3 ≤ N ≤ 105
  • 1 ≤ Q ≤ 105
  • 1 ≤ u, vN
  • 1 ≤ Di ≤ 105 for all i
  • Di ≤ 105 (1 ≤ iQ)
  • 1 ≤ ajN for all j in every variation

서브태스크

번호배점제한
19

Q = 1, there is an edge between node 1 and i for every i (2 ≤ iN) Flóra doesn’t add any extra leaves to node 1

29

Q = 1, there is an edge between node i and i + 1 for all i (1 ≤ i < N) Flóra doesn’t add any extra leaves to node 1, nor node N

316

N ≤ 20000 and Q ≤ 300

419

The original tree is a perfect binary tree rooted at node 1 (i.e. each internal node has exactly 2 children, and every leaf has the same distance from the root)

517

Di = 1 for all i

630

No additional constraints

예제 입력 1

7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1

예제 출력 1

-1
10
8

힌트

The following picture shows the second variation.

A possible solution is to clean the path between leaves 1 − 6, A − 7 and B − 3.

채점 및 기타 정보

  • 예제는 채점하지 않는다.