Майже найкоротший шлях#10116
У вас є неорієнтований неваговий граф з двома виділеними вершинами і . Відстань найкоротшого шляху між і позначимо як . Майже найкоротший шлях від до — це шлях найменшої можливої довжини, який не використовує жодного ребра, що може бути частиною шляху довжини . Ваше завдання — знайти довжину цього майже найкоротшого шляху або вивести -1, якщо такий шлях не існує.
Перший рядок містить чотири цілі числа: кількість вершин , кількість ребер (, m \le 10^5), а також номери вершин і (1 \le s, t \le n). Кожен з наступних рядків містить два цілі числа і , які визначають неорієнтоване ребро (, ).
Виведіть довжину майже найкоротшого шляху між вершинами і . Якщо такого шляху не існує, виведіть -1.
Приклад 1
Найкоротший шлях між вершинами і має довжину . Ребра, які можуть бути частиною найкоротшого шляху, виділені червоним. Майже найкоротший шлях — це найкоротший шлях, що не проходить через жодне з цих червоних ребер. Він виділений синім кольором, і його довжина становить .