Найдите кратчайшее расстояние между парой вершин в неориентированном графе. Граф может быть несвязным.
В первой строке дано количество вершин n (1 ≤ n ≤ 105) и рёбер m (1 ≤ m ≤ 105). Далее в m строках описаны рёбра графа. Каждое ребро описывается номерами двух вершин u и v (1 ≤ u, v ≤ n). В последней строке дан номер стартовой вершины s (1 ≤ s ≤ n) и конечной t (1 ≤ t ≤ n).
Гарантируется, что в графе нет петель и кратных рёбер.
Выведите длину кратчайшего пути (в рёбрах) между заданной парой вершин. Если пути не существует, то выведите -1.
|
5 5 2 4 3 5 2 1 2 3 4 5 1 5 |
3 |
|
4 3 2 3 4 3 2 4 1 3 |
-1 |
|
2 1 2 1 1 1 |
0 |