e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Azerbaijan Student Finals

Поджог

Перед Вами самая обычная паутина. Однако, как опытный олимпиадник, Вы заметили, что она представляет собой связный граф с n вершинами и m ребрами. Если поджечь какую-нибудь вершину, то она загорится, через секунду загорятся все смежные с ней, потом загорятся все смежные с уже горящими и т.д.

Вам известно, в каких вершинах подожгут паутину (во всех одновременно). Нужно найти, сколько секунд пройдет, пока загорится последняя вершина и какая это будет вершина.

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

В первой строке натуральные числа n (1n105) и m (n - 1m105). Далее m строк, в каждой по два числа – номера вершин, которые являются концами ребра. Вершины нумеруются с 1.

В следующей строке задано число k (1kn) – количество точек поджога. В следующей строке содержатся номера k вершин, которые поджигаются.

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

В первой строке выведите время, когда загорится последняя вершина. Во второй строке выведите номер этой вершины. Если таких несколько, выведите ту, у которой номер минимальный.

prb4369.gif

Лимит времени 1 секунд
Лимит использования памяти 128 MiB
Входные данные #1
6 6
1 2
2 6
1 5
5 6
3 5
4 5
2
1 2
Выходные данные #1
2
3
Автор Андрей Селиванов
Источник "Пятёрка за неделю" 05 2013-2014. Поиск в ширину