C. Сам кратчайший путь
3000 мс · 256 МБ · всё или ничего
Неориентированный граф задан списком рёбер. Найдите кратчайший путь из вершины в вершину .
Кратчайших путей может быть несколько; выведите лексикографически наименьший как последовательность номеров вершин.
Приём: посчитать расстояния обходом от , а потом идти от , каждый раз выбирая наименьшего соседа, расстояние которого на единицу меньше текущего. Так каждый шаг остаётся на кратчайшем пути, а из подходящих берётся наименьший номер.
Формат ввода
Первая строка содержит числа (), (), и .
Далее идут строк с рёбрами.
Формат вывода
Если пути нет, выведите .
Иначе в первой строке — количество вершин в пути, во второй — сам путь.
Примеры
ввод
5 4 1 5 1 2 1 3 2 4 3 5
вывод
3 1 3 5
ввод
6 6 1 6 1 2 2 6 1 3 3 6 1 4 4 6
вывод
3 1 2 6
Войдите, чтобы отправлять решения.