Задачі
Кратчайший четный путь
Кратчайший четный путь
Задан неориентированный граф. Найдите кратчайший путь между двумя вершинами четной длины.
\InputFile
Первая строка содержит четыре целых числа: количество вершин $n$, количество ребер $m~(n, m \le 10^5)$ и номера вершин $s$ и $d~(1 \le s, d \le n)$. Каждая из следующих $m$ строк содержит два целых числа $a$ и $b$ задающих неориентированное ребро $(a, b)$.
\OutputFile
Выведите кратчайший путь между вершинами $s$ и $d$. Длина пути (количество ребер в пути) должна быть четной. Если пути четной длины между $s$ и $d$ не существует, то выведите $-1$.
\includegraphics{https://static.e-olymp.com/content/6a/6adee2ac9b12616702d7346fe468c745baa3b60c.gif}
Вхідні дані #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