|
Из-за участившихся раскрытий своих агентов, Комитет Государственной Безопасности Бутыляндии решил провести реформу, направленную на улучшение их деятельности. Первым делом необходимо обеспечить безопасность встреч агентов. Ваша программа должна помочь в решении этой проблемы. Вам дано описание путей в Бутыляндии и начальные положения двух агентов. Ваша программа должна ответить, возможно ли безопасная встреча этих агентов.
Чтобы быть в безопасности агенты должны соблюдать такие условия:
- Агенты двигаются в течение дня, и встречаются вечером,
- Агент должен изменять место пребывания каждый день,
- Агенты могут путешествовать только по дорогам, соединяющим города (в Бутыляндии имеются односторонние дороги),
- Агент не может двигаться слишком быстро (это может выглядеть очень подозрительным) - в течение одного дня он не может путешествовать дальше, чем в соседний город,
- Расстояние между двумя связанными городами настолько коротко, что агент, отправившись от одного города утром, достигнет другого вечером,
- Встречей называется такое состояние, когда два агента находятся в том же самом городе в тот же самый вечер.
Ваша программа должна
- Читать число городов и описания сети путей в Бутыляндии и стартовые положения агентов,
- Проверять, возможна ли безопасная встреча, и если так, то через сколько дней,
- Выводит результат
Входные данные
В первой строке вводятся два целых числа n и m, разделенные пробелом, где 1 <= n <= 250, 0 <= m <= n * (n-1).
Во второй строке даны два целых числа a1 и a2, разделенные пробелом, 1 <= a1, a2 <= n и a1 <> a2. a1 и a2 стартовые положения агентов Номер 1 и Номер 2.
В m следующих строк даны пары чисел a и b, разделенные пробелом, 1 <= a, b <= n и a <> b. Эти числа означают, что имеется путь от города a к городу b.
Выходные данные:
Единственная строка должна содержать:
- Одно положительное целое число, которое является минимальным временем (в днях) необходимым, чтобы устроить безопасную встречу двух агентов, если она возможна,
- Слово NIE (НЕ в польском), если такая встреча невозможна.
Пример
Ввод:
6 7
1 5
1 2
4 5
2 3
3 4
4 1
5 4
5 6
Вывод:
3
|
