Byteasar el Vendedor Ambulante


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Swift, VB

Un vendedor Byteasar trabaja duro viajando por Byteotia. En tiempos pasados, los vendedores ambulantes podían elegir las ciudades que querían visitar y el orden en hacerlo, pero esos tiempos se han ido para siempre. Desde el momento en que se estableció la Oficina Central de Control para Vendedores Viajeros, cada vendedor recibe de la Oficina una lista de ciudades para visitar y el orden de su recorrido. Como suele suceder con las oficinas centrales, el orden impuesto de visitar las ciudades no tiene mucho en común con un orden óptimo. Antes de partir para su gira, Byteasar quisiera saber al menos cuánto tiempo le llevará visitar todas las ciudades. Es su tarea calcular esto.

Las ciudades de Byteotia están numeradas del 1 a N. La capital de Byteotia tiene el número 1, y este es el lugar desde el cual Byteasar comienza su viaje. Las ciudades están conectadas por una red de caminos de dos vías. Un viaje entre dos ciudades conectadas directamente por una carretera siempre lleva 1 unidad de tiempo. Desde la capital se puede llegar a cualquier otra ciudad byteotiana. Sin embargo, la red de carreteras se había diseñado de manera muy económica, por lo que las carreteras nunca forman ciclos.

Escriba un programa que lea la descripción de la red de carreteras en Byteotia y la lista de ciudades que Byteasar tiene que visitar y calcule el tiempo total de viaje de Byteasar.

Entrada

En la primera línea de la entrada hay un número entero N igual al número de ciudades en Byteotia, 1 \leq N \leq 30 000. En las siguientes líneas N - 1 se describe la red de carreteras. En cada una de estas líneas hay dos enteros a y b \((1 \leq a, b \leq N; a ≠ b)\), lo que significa que las ciudades a y b están conectadas por una carretera. En la línea N + 1 hay un número entero M igual al número de ciudades que Byteasar debería visitar, 1 \leq M \leq 5 000. En las siguientes líneas M hay números de ciudades sucesivas en la ruta de Byteasar: un número por línea.

Salida

En la primera y única línea de la salida debería haber un número entero igual al tiempo total del viaje de Byteasar.

Ejemplo de Entrada

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

Ejemplo de Salida

7

Comments

There are no comments at the moment.