Роботы устроены так, что, получив команду, они все начали двигаться с такой скоростью, что туннель между двумя любыми залами преодолевают за 1 минуту. Роботы не могут останавливаться (в том числе и в залах), а также менять направление движения, находясь в туннелях (однако попав в зал робот может из него пойти по тому же туннелю, по которому он пришел в этот зал).
Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).
Формат входных данных
Во входном файле записаны сначала числа N — количество залов (1N400) и K — количество туннелей (1K20000). Далее записано K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами возможно несколько туннелей. Туннель может соединять зал с самим собой. Далее записано число M (1M400) — количество роботов. Затем идет M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.
Формат выходных данных
В выходной файл выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).
Примеры
f.in
f.out
4 5
1 2
2 3
3 4
1 4
1 3
3
1 2 4
1
3 3
1 2
2 3
3 1
3
1 2 3
1.5
В какую сторону двигаться?
А еще, где можно взять решения задач с IX Московской командной олимпиады школьников по программированию (проходившей в 2005 году)?
Сообщение отредактировано: Nezhny_Vampir -