| Codeforces Round 328 (Div. 2) |
|---|
| Закончено |
На самом деле Ари — не совсем обычное чудовище. Она представляет собой скрытую личность Супер М, одного из главных супергероев Байтфорсес. Байтфорсес — это страна, состоящая из n городов, соединенных n - 1 дорогами. Каждая дорога соединяет ровно два различных города, и вся дорожная система разработана так, что можно добраться от любого города до любого другого города, используя только данные дороги.
На m городов напали злые люди. И вот, Ари... то есть, Супер М должен немедленно направиться в каждый из атакуемых городов, чтобы прогнать злых людей. Супер М может перемещаться между городами только используя данные дороги. Более того, перемещение по любой из дорог занимает у неё ровно один крон (единица времени, используемая в Байтфорсес).
Однако, сейчас Супер М не в Байтфорсес — она посещает тренировочный лагерь, расположенный в близлежащей стране Кодфорсес. К счастью, в Кодфорсес есть особый прибор, позволяющий мгновенно телепортировать девушку из Кодфорсес в любой город Байтфорсес. Обратный путь слишком долог, так что в рамках данной задачи телепортация используется ровно один раз.
Вам следует помочь Супер М и вычислить город, в который она должна телепортироваться в начале, чтобы завершить свою работу за минимальное время (измеряемое в кронах). Также сообщите ей это время, чтобы она могла распланировать дорогу обратно в Кодфорсес.
В первой строке входных данных записаны два целых числа n и m (1 ≤ m ≤ n ≤ 123456) — количество городов в Байтфорсес, и количество атакуемых городов, соответственно.
Далее следует n - 1 строка, описывающая систему дорог. Каждая строка состоит из двух номеров городов ui и vi (1 ≤ ui, vi ≤ n) — концы очередной дороги.
Последняя строка содержит m различных целых чисел — номера атакуемых городов. Эти числа даны в произвольном порядке.
Сперва выведите номер города, куда надо телепортироваться Супер М. Если оптимальных ответов несколько, выведите город с наименьшим номером.
Затем выведите наименьшее возможное время, необходимое для того, чтобы распугать всех людей в атакуемых городах, измеренное в кронах.
Обратите внимание, что правильный ответ всегда единственен.
7 2
1 2
1 3
1 4
3 5
3 6
3 7
2 7
2
3
6 4
1 2
2 3
2 4
4 5
4 6
2 4 5 6
2
4
В первом примере есть две возможности завершить работу Супер М за 3 крона:
and 
.
Однако вам следует выбрать первый вариант, так как он начинается в городе с меньшим номером.
