Задачі
Найкоротший шлях
Найкоротший шлях
Задано неорієнтовний граф. Знайдіть найкоротший шлях від вершини a до вершини b.
Вхідні дані
У першому рядку знаходиться два цілих числа n та m (1 ≤ n ≤ 5 * 104
, 1 ≤ m ≤ 105
) - кількість вершин та ребер відповідно. У другому рядку йдуть цілі числа 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