|
Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.
Бонни и Клайд ограничение по времени на тест 2 секундыограничение по памяти на тест 64 мегабайтаввод стандартный вводвывод стандартный выводДобро пожаловать в один не слишком известный штат одной слишком известной страны. Здесь, среди прерий, мирно существуют N небольших городов, соединённых дорожной сетью. Но мало кто знает, что именно в этих местах сейчас скрываются от рейнджеров знаменитые грабители Бонни и Клайд! Чтобы уйти от преследования, парочке пришлось разделиться, и в итоге Бонни оказалась в городе X, а Клайд — в городе Y. Теперь они хотят как можно скорее встретиться друг с другом, а для этого им нужно одновременно оказаться в одном и том же городе. Но ни один из них не может сидеть на месте и ждать другого: полиция идёт по следу, поэтому каждый день и Бонни, и Клайд вынуждены перемещаться в один из соседних городов. Попробуйте выяснить, смогут ли Бонни и Клайд наконец воссоединиться, и если да, то как скоро это произойдёт. Входные данные Первая строка содержит целые числа N и M (1 ≤ N ≤ 100, Следующие M строк описывают дороги. Каждая из них содержит целые числа Ai и Bi (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi) — номера городов, которые соединяет дорога. Гарантируется, что между каждой парой городов существует не более одной дороги, а также что из любого города можно добраться по дорогам до всех остальных. Следующая строка содержит целые числа X и Y (1 ≤ X, Y ≤ N) — соответственно номер города, в котором находится Бонни, и номер города, в котором находится Клайд. Выходные данные Выведите одно целое число — минимальное количество дней, через которое Бонни и Клайд смогут одновременно оказаться в одном городе. Если Бонни и Клайд не сумеют встретиться, выведите -1. Примеры Входные данные 7 8 Выходные данные 3 Входные данные 5 5 Выходные данные -1 Для отправки решений необходимо выполнить вход. |