e-olymp
Соревнования

Azerbaijan Student Finals

Поджог

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

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

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

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

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

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

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

Лимит времени 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. Поиск в ширину