Майже найкоротший шлях

У вас є неорієнтований неваговий граф з двома виділеними вершинами s і t. Відстань найкоротшого шляху між s і t позначимо як d. Майже найкоротший шлях від s до t — це шлях найменшої можливої довжини, який не використовує жодного ребра, що може бути частиною шляху довжини d. Ваше завдання — знайти довжину цього майже найкоротшого шляху або вивести -1, якщо такий шлях не існує.

Вхідні дані

Перший рядок містить чотири цілі числа: кількість вершин n, кількість ребер m (n, m ≤ 10^5), а також номери вершин s і t (1 ≤ s, t ≤ n). Кожен з наступних m рядків містить два цілі числа a і b, які визначають неорієнтоване ребро (a, b).

Вихідні дані

Виведіть довжину майже найкоротшого шляху між вершинами s і t. Якщо такого шляху не існує, виведіть -1.

Приклади

Примітка

Найкоротший шлях між вершинами 1 і 3 має довжину 2. Ребра, які можуть бути частиною найкоротшого шляху, виділені червоним. Майже найкоротший шлях — це найкоротший шлях, що не проходить через жодне з цих червоних ребер. Він виділений синім кольором, і його довжина становить 5.