E. Агент 211
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Клуб Творчества Программистов ПетрГУ проводит очередные сборы по программированию! Руководитель клуба пришёл в кабинет КТП IT-парка ПетрГУ незадолго до начала первого контеста сборов, чтобы убедиться что всё готово, и обнаружил, что в процессе подготовки сборов все забыли подготовить кабинет – не хватает компьютеров, мониторов, клавиатур и мышей, принтера и бумаги, и даже чайника, чтобы команды могли пить чай.

Быстро взяв себя в руки, он написал об этой проблеме в обще-айтипарковский чат и выяснил, что может быстро собрать всё необходимое для сборов в разных кабинетах IT-парка.

IT-парк ПетрГУ – это странный архитектурный комплекс, который представляет собой $$$n+1$$$ кабинетов, соединённых между собой проходами. Известно, что:

  • между двумя кабинетами не может быть больше одного прохода;
  • из каждого кабинета можно попасть в каждый другой, возможно проходя сквозь другие кабинеты;
  • по IT-парку из-за планировки не получится ходить кругами: если идти из кабинета КТП в какой-то другой кабинет, обратно идти получится ровно по тем же самым кабинетам и никак иначе.

Итак, руководитель КТП находится в кабинете под номером $$$b_1$$$ и должен посетить другие кабинеты с номерами $$$b_2, ..., b_m$$$ без какого-то определённого порядка и вернуться обратно в кабинет $$$b_1$$$ как можно быстрее.

Сколько времени у него на это уйдёт, если переход между кабинетами занимает одну единицу времени?

Входные данные

В первой строке ввода дано целое положительное число $$$n$$$ – количество проходов между кабинетами, $$$n \lt 10^5$$$.

В следующих $$$n$$$ строках дано по два целых положительных числа $$$a_i$$$ $$$a_j$$$, которые означают что существует проход между кабинетами с номерами $$$a_i$$$ и $$$a_j$$$, где $$$a_i \ne a_j$$$ и $$$a_i, a_j \le n+1$$$.

В следующий строке дано целое положительное число $$$m$$$ – количество кабинетов, которые необходимо посетить, $$$m \le n+1$$$.

В следующей строке дано $$$m$$$ целых положительных чисел $$$b_i$$$ – номера кабинетов, которые необходимо посетить, $$$b_i \le n+1$$$.

Выходные данные

Выведите единственное целое число – ответ на задачу.

Система оценки
Группа тестовДополнительные ограниченияБаллыНеобходимые группы
$$$m$$$План IT-парка ПетрГУ
$$$1$$$—Кабинеты соединены и35—
пронумерованы последовательно
(см. первый пример)
$$$2$$$$$$m = 2$$$—35
$$$3$$$——30$$$1$$$, $$$2$$$

Обратите внимание, что для прохождения групп тестов ваша программа не обязана выдавать верный ответ на примерах из условия.

Примеры
Входные данные
4
1 2
2 3
3 4
4 5
3
3 1 4
Выходные данные
6
Входные данные
4
1 2
3 2
4 2
4 5
3
3 1 4
Выходные данные
6
Примечание

В первом примере кабинеты соединены в цепочку и пронумерованы последовательно.

Можно совершить, например, следующие переходы:

  1. из кабинета 3 в кабинет 4 – за время 1 ($$$3 \rightarrow 4$$$)
  2. из кабинета 4 в кабинет 1 – за время 3 ($$$4 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$)
  3. из кабинета 1 в кабинет 3 – за время 2 ($$$1 \rightarrow 2 \rightarrow 3$$$)

В итоге на весь путь уйдёт 6 единиц времени.

Во втором примере можно совершить, например, следующие переходы:

  1. из кабинета 3 в кабинет 4 – за время 2 ($$$3 \rightarrow 2 \rightarrow 4$$$)
  2. из кабинета 4 в кабинет 1 – за время 2 ($$$4 \rightarrow 2 \rightarrow 1$$$)
  3. из кабинета 1 в кабинет 3 – за время 2 ($$$1 \rightarrow 2 \rightarrow 3$$$)

В итоге на весь путь уйдёт 6 единиц времени.