EduBrick

C. Сам кратчайший путь

3000 мс · 256 МБ · всё или ничего

Неориентированный граф задан списком рёбер. Найдите кратчайший путь из вершины aa в вершину bb.

Кратчайших путей может быть несколько; выведите лексикографически наименьший как последовательность номеров вершин.

Приём: посчитать расстояния обходом от bb, а потом идти от aa, каждый раз выбирая наименьшего соседа, расстояние которого на единицу меньше текущего. Так каждый шаг остаётся на кратчайшем пути, а из подходящих берётся наименьший номер.

Формат ввода

Первая строка содержит числа nn (1≤n≤1051 \le n \le 10^5), mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5), aa и bb.

Далее идут mm строк с рёбрами.

Формат вывода

Если пути нет, выведите −1-1.

Иначе в первой строке — количество вершин в пути, во второй — сам путь.

Примеры

ввод
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
Войдите, чтобы отправлять решения.