eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Задан неориентированный невзвешенный граф, в котором выделены две вершины s и t. Пусть величина кратчайшего пути от s к t равна d. Почти кратчайшим путем от s к t назовем такой путь наименьшей длины, который не проходит ни по одному ребру, по которому может проходить путь длины d. Найдите длину почти кратчайшего пути или выведите -1 если такого пути не существует.

Giriş verilənləri

Первая строка содержит четыре целых числа: количество вершин n, количество ребер m (n, m10^5) и номера вершин s и t (1s, tn). Каждая из следующих m строк содержит два целых числа a и b задающих неориентированное ребро (a, b).

Çıxış verilənləri

Выведите длину почти кратчайшего пути между вершинами s и t. Если такого пути не сущестует, то вывести -1.

Nümunə

Giriş verilənləri #1
6 9 1 3
1 5
4 5
4 1
1 2
4 2
2 6
2 3
3 6
3 4
Çıxış verilənləri #1
5

Qeyd

prb10116.gif

Кратчайший путь между вершинами 1 и 3 равен 2. Ребра, через которые может проходить кратчайший путь, выделены красным. Почти кратчайший путь - это кратчайший путь, не проходящий ни по одному из красных ребер. Почти кратчайший путь выделен синим цветом, его длина равна 5.

Müəllif Михаил Медведев