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

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

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

Первая строка содержит четыре целых числа: количество вершин $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$.

Примеры