Почти кратчайший путь

Задан неориентированный невзвешенный граф, в котором выделены две вершины 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.