e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

Кратчайший путь

Кратчайший путь

Задан неориентированный граф. Найдите кратчайший путь от вершины a до вершины b.

Входные данные

В первой строке находится два целых числа n и m (1n5 * 104, 1m105) - количества вершин и рёбер соответственно. Во второй строке заданы целые числа a и b - стартовая и конечная вершина соответственно. Далее идут m строк, описывающие рёбра.

Выходные данные

Если пути между a и b нет, то выведите -1. Иначе выведите в первой строке длину l кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите l + 1 число - вершины этого пути.

prb4853.gif

Лимит времени 2 секунда
Лимит использования памяти 128 MiB
Входные данные #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