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

Кратчайший четный путь

Кратчайший четный путь

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

Задан неориентированный граф. Найдите кратчайший путь между двумя вершинами четной длины.

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

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

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

Выведите кратчайший путь между вершинами s и d. Длина пути (количество ребер в пути) должна быть четной. Если пути четной длины между s и d не существует, то выведите -1.

Пример

Входные данные #1
8 8 1 6
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 6
Выходные данные #1
6
Входные данные #2
6 5 1 6
1 2
2 3
3 4
4 5
5 6
Выходные данные #2
-1
Автор Михаил Медведев