F. Путь между вершинами
3000 мс · 256 МБ · всё или ничего
Неориентированный граф задан списком рёбер. Найдите какой-нибудь путь из вершины в вершину .
Обход в глубину кратчайший путь не даёт — за кратчайшим придётся подождать до следующего занятия. Зато он легко даёт хоть какой-то путь: достаточно запомнить, из какой вершины мы впервые пришли в каждую, и подняться по этим ссылкам от к .
Чтобы ответ был единственным, обход должен идти из и перебирать соседей по возрастанию номера.
Формат ввода
Первая строка содержит числа (), (), и .
Далее идут строк с рёбрами.
Формат вывода
Если пути нет, выведите .
Иначе в первой строке выведите количество вершин в пути, во второй — сам путь от к .
Примеры
ввод
5 4 1 5 1 2 1 3 2 4 3 5
вывод
3 1 3 5
ввод
4 2 1 4 1 2 3 4
вывод
-1
Войдите, чтобы отправлять решения.