Парк
Обмеження: 2 сек., 256 МіБ
Зеник і Марічка гуляли парком дуужее довго, і в один момент Зеник помітив, що Марічка кудись зникла. Він хоче якомога швидше її знайти і просить у вас допомоги.
Зеник знає, що парк складається з \(n\) галявин і \(n-1\) стежок, які ведуть від однієї галявини до іншої. Стежки протоптані таким чином, що з будь-якої галявини можна дійти до будь-якої іншої, пересуваючись лише стежками.
Зараз Зеник стоїть на галявині з номером 0, а Марічка чекає на нього на випадковій галявині. Також Зеник знає, що на \(m\) галявинах з номерами \(e_i\) гуляють колишні хлопці Марічки, і вона точно не там. У парку є як мінімум 1 галявина, на якій немає її колишнього.
Маючи цю інформацію, підкажіть Зенику, за який мінімальний час Зеник зможе гарантовано знайти Марічку за умови, що прохід однією стежкою займає 1 хвилину.
Вхідні дані
У першому рядку задано два цілих числа \(n\) i \(m\) — кількість галявин та кількість галявин, на яких гуляють колишні хлопці Марічки.
У наступному рядку записано \(m\) цілих чисел \(e_i\) — номери галявин, на яких гуляють колишні. Усі номери унікальні.
У наступних \(n-1\) рядках записано по два числа через пробіл \(u_i\) й \(v_i\) — номери галявин, які з’єднані стежками.
Галявини номеруються з 0.
Вихідні дані
В одному рядку виведіть ціле число — мінімальний час у хвилинах, за який Зеник гарантовано знайде Марічку.
Обмеження
\(2 \le n \le 5 \cdot 10^{5}\),
\(0 \le m \le n-2\),
\(0 \le e_{i} \le n-1\),
\(0 \le u_i, v_i \le n-1\),
\(u_i \ne v_i\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
3 0 0 1 0 2 | 3 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
7 3 0 3 6 0 1 1 6 0 2 2 3 2 4 3 5 | 7 |
Примітки
У першому прикладі Зеник може гарантовано знайти Марічку, якщо обійде всі галявини. Одним з найкоротших шляхів, щоб це зробити, є \(0 \to 1 \to 0 \to 2\).
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|