Найкоротший парний шлях

Задано неорієнтований граф. Знайдіть найкоротший шлях парної довжини між двома вершинами.

Вхідні дані

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

Приклади