e-olymp
Задачи

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

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

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

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

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

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

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

Лимит времени 1 секунда
Лимит использования памяти 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