EduBrick

F. Путь в ориентированном графе

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

Ориентированный граф задан списком рёбер. Найдите путь из вершины aa в вершину 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 строк с парами (u,v)(u, v).

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

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

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

Примеры

ввод
4 3 1 3
1 2
2 3
4 1
вывод
3
1 2 3
ввод
3 2 1 3
2 1
3 1
вывод
-1
Войдите, чтобы отправлять решения.