F. Фабрика деревьев
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Байтландская фабрика деревьев производит деревья для всевозможных промышленных применений. Вам требуется соптимизировать построение дерева определённого типа для большого и важного заказа.

Нужное дерево является подвешенным деревом с $$$n$$$ вершинами, и его вершины пронумерованы различными числами от $$$0$$$ до $$$n - 1$$$. Вершина с номером $$$0$$$ является корнем дерева, и для любой некорневой вершины $$$v$$$ номер её родителя $$$p(v)$$$ меньше номера $$$v$$$.

Все деревья на фабрике делаются из заготовок-бамбуков. Бамбук — это такое корневое дерево, что каждая вершина имеет ровно одного сына, кроме единственной вершины-листа, у которой нет детей. Вершины бамбука-заготовки могут быть пронумерованы как угодно до начала обработки.

Чтобы превратить бамбук в нужное дерево, вы можете применять один тип операций: выбрать произвольную некорневую вершину $$$v$$$, такую что её родитель $$$p(v)$$$ также не является корнем. Операция состоит в изменении родителя $$$v$$$ на родителя его родителя $$$p(p(v))$$$. Родители всех остальных вершин остаются без изменений, в частности, поддерево $$$v$$$ не меняется.

Эффективность крайне важна, поэтому вам требуется минимизировать количество операций для превращения бамбука-заготовки в нужное дерево. Постройте любую оптимальную последовательность операций.

Обратите внимание, что нумерация вершин в полученном дереве должна совпадать с нумерацией в данном дереве. Формально, номера корней должны совпадать, а также для некорневых вершин с одинаковыми номерами должны совпадать номера их родителей.

Гарантируется, что во всех тестах к этой задаче ответ существует, и, более того, в оптимальной последовательности не более $$$10^6$$$ операций. Обратите внимание, что любой взлом, не удовлетворяющий этим ограничениям, будет некорректным.

Входные данные

В первой строке записано единственное целое число $$$n$$$ — количество вершин дерева ($$$2 \leq n \leq 10^5$$$).

Во второй строке записано $$$n - 1$$$ целое число $$$p(1), \ldots, p(n - 1)$$$ — номера родителей вершин $$$1, \ldots, n - 1$$$ соответственно ($$$0 \leq p(i) < i$$$).

Выходные данные

В первой строке выведите $$$n$$$ различных целых чисел $$$id_1, \ldots, id_n$$$ — изначальная нумерация вершин бамбука-заготовки, начиная с корня ($$$0 \leq id_i < n$$$).

Во второй строке выведите одно целое число $$$k$$$ — количество операций в вашей последовательности ($$$0 \leq k \leq 10^6$$$).

В третьей строке выведите $$$k$$$ целых чисел $$$v_1, \ldots, v_k$$$, описывающих операции по порядку. $$$i$$$-я операция состоит в изменении $$$p(v_i)$$$ на $$$p(p(v_i))$$$. Каждая операция должна быть корректной, т.е. $$$v_i$$$ и $$$p(v_i)$$$ на момент операции не могут быть корнем.

Примеры
Входные данные
5
0 0 1 1
Выходные данные
0 2 1 4 3
2
1 3
Входные данные
4
0 1 2
Выходные данные
0 1 2 3
0