## An Animal Contest 2 P6 - Koala Transport System

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Java 2.0s
Python 2.0s
Memory limit: 256M
Python 512M

Author:
Problem types

Lately, the koalas have noticed that their feeding grounds are too far away from their home so they have decided to find a better way to move between their destinations. Lucky for them, you have a bunch of teleporters lying around, so they hire you to fix their problem!

The koalas live in a forest of connected trees, numbered from to , joined by branches that can be crossed in either direction in minute; each tree is a possible feeding ground. The koalas' home is tree . On each of the next days, the koalas will have a new set of distinct feeding grounds, with the feeding ground designated as .

A teleportation plan for the koalas will be built daily. To do so, we will first choose any tree . Then, on all the trees on the unique simple path from tree to tree , we will install a teleporter; a teleporter allows for instant travel to any other teleporter. Note that teleporters only last for one day and a plan must be redesigned every day.

Each day, koalas populate all feeding grounds designated for that day, and every evening, all koalas need to return home. Among all possible teleportation plans, you are to find one that allows all the koalas to return to tree using the minimum total time and report this number to the chief koala!

For this problem, Python users are recommended to use PYPY over CPython.

#### Constraints

For this problem, you will NOT be required to pass the sample cases in order to receive points.

For each day, all are distinct.

The sum of over all days is guaranteed to be less than or equal to .

#### Input Specification

The first line contains two space-separated integers and .

The next lines each contains 2 integers and , indicating a bidirectional branch between trees and .

lines follow, with lines for each day. The first line for each day contains , followed by integers on the next line, representing the designated feeding grounds for day .

#### Output Specification

Output lines, the of which contains the minimum time for the day.

#### Sample Input 1

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

#### Sample Output 1

3
0

#### Explanation for Sample 1

For the first day, the optimal is , and the teleporters will be installed on trees , and . Since tree is already on the path, its distance is . Tree is branch away from its closest teleporter (tree ) and tree is branches away from its closest teleporter at tree . Therefore the answer is minutes.

For the second day we again choose . Since teleporters are installed on all feeding grounds, the answer is .

#### Sample Input 2

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

#### Sample Output 2

1
0