Задачи
Кратчайший четный путь
Кратчайший четный путь
Задан неориентированный граф. Найдите кратчайший путь между двумя вершинами четной длины.
Входные данные
Первая строка содержит четыре целых числа: количество вершин 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