Central-European Olympiad in Informatics, CEOI 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Spring cleaning

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSpring 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 $$$D_i$$$ 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.

Input

The first line contains two space-separated integer, $$$N$$$ and $$$Q$$$ ($$$3 \leq N \leq 10^{5}$$$, $$$1 \leq Q \leq 10^{5}$$$) – the number of nodes the tree has and the number of variations.

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 ($$$1 \leq u, v \leq N$$$).

The next $$$Q$$$ lines describe the variations. The first integer in the $$$i$$$th line is $$$D_i$$$ ($$$1 \leq D_i \leq 10^{5}$$$). Then $$$D_i$$$ space-separated integers follow: if the $$$j$$$th number is $$$a_j$$$, it means that Flóra adds a new leaf to node $$$a_j$$$ ($$$1 \leq a_j \leq N$$$). We may add more than one leaf to the same node. $$$\sum_{1}^{Q} D_i \leq 10^{5}$$$ i.e. the sum of $$$D_i$$$ in all varations is at most $$$10^5$$$.

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

Output

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$$$.

Scoring

Example

Input

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

Output

-1 10 8

Note

The following picture shows the second variation. A possible solution is to clean the path between leaves $$$1 - 6$$$, $$$A - 7$$$ and $$$ B - 3$$$.

You can download the above example and an additional (bigger) sample input here: https://gofile.io/d/8QlbsS

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2021 05:37:16 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|