eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Почти кратчайший путь

Почти кратчайший путь

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Задан неориентированный невзвешенный граф, в котором выделены две вершины s и t. Пусть величина кратчайшего пути от s к t равна d. Почти кратчайшим путем от s к t назовем такой путь наименьшей длины, который не проходит ни по одному ребру, по которому может проходить путь длины d. Найдите длину почти кратчайшего пути или выведите -1 если такого пути не существует.

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

Первая строка содержит четыре целых числа: количество вершин n, количество ребер m (n, m10^5) и номера вершин s и t (1s, tn). Каждая из следующих m строк содержит два целых числа a и b задающих неориентированное ребро (a, b).

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

Выведите длину почти кратчайшего пути между вершинами s и t. Если такого пути не сущестует, то вывести -1.

Пример

Входные данные #1
6 9 1 3
1 5
4 5
4 1
1 2
4 2
2 6
2 3
3 6
3 4
Выходные данные #1
5

Примечание

prb10116.gif

Кратчайший путь между вершинами 1 и 3 равен 2. Ребра, через которые может проходить кратчайший путь, выделены красным. Почти кратчайший путь - это кратчайший путь, не проходящий ни по одному из красных ребер. Почти кратчайший путь выделен синим цветом, его длина равна 5.

Автор Михаил Медведев