EduBrick

F. Путь между вершинами

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

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

Обход в глубину кратчайший путь не даёт — за кратчайшим придётся подождать до следующего занятия. Зато он легко даёт хоть какой-то путь: достаточно запомнить, из какой вершины мы впервые пришли в каждую, и подняться по этим ссылкам от bb к aa.

Чтобы ответ был единственным, обход должен идти из 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.

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

Примеры

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