Задачи
Кратчайший путь
Кратчайший путь
Задан неориентированный граф. Найдите кратчайший путь от вершины a до вершины b.
Входные данные
В первой строке находится два целых числа n и m (1 ≤ n ≤ 5 * 10^4, 1 ≤ m ≤ 10^5) - количества вершин и рёбер соответственно. Во второй строке заданы целые числа a и b - стартовая и конечная вершина соответственно. Далее идут m строк, описывающие рёбра.
Выходные данные
Если пути между a и b нет, то выведите -1. Иначе выведите в первой строке длину l кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите l + 1 число - вершины этого пути.
Пример
Входные данные #1
4 5 1 4 1 3 3 2 2 4 2 1 2 3
Выходные данные #1
2 1 2 4
Входные данные #2
4 4 2 3 2 1 2 4 4 3 1 3
Выходные данные #2
2 2 1 3