Байтландская фабрика деревьев производит деревья для всевозможных промышленных применений. Вам требуется соптимизировать построение дерева определённого типа для большого и важного заказа.
Нужное дерево является подвешенным деревом с \(n\) вершинами, и его вершины пронумерованы различными числами от \(0\) до \(n - 1\). Вершина с номером \(0\) является корнем дерева, и для любой некорневой вершины \(v\) номер её родителя \(p(v)\) меньше номера \(v\).
Все деревья на фабрике делаются из заготовок-бамбуков. Бамбук — это такое корневое дерево, что каждая вершина имеет ровно одного сына, кроме единственной вершины-листа, у которой нет детей. Вершины бамбука-заготовки могут быть пронумерованы как угодно до начала обработки.
Чтобы превратить бамбук в нужное дерево, вы можете применять один тип операций: выбрать произвольную некорневую вершину \(v\), такую что её родитель \(p(v)\) также не является корнем. Операция состоит в изменении родителя \(v\) на родителя его родителя \(p(p(v))\). Родители всех остальных вершин остаются без изменений, в частности, поддерево \(v\) не меняется.
Эффективность крайне важна, поэтому вам требуется минимизировать количество операций для превращения бамбука-заготовки в нужное дерево. Постройте любую оптимальную последовательность операций.
Обратите внимание, что нумерация вершин в полученном дереве должна совпадать с нумерацией в данном дереве. Формально, номера корней должны совпадать, а также для некорневых вершин с одинаковыми номерами должны совпадать номера их родителей.
Гарантируется, что во всех тестах к этой задаче ответ существует, и, более того, в оптимальной последовательности не более \(10^6\) операций. Обратите внимание, что любой взлом, не удовлетворяющий этим ограничениям, будет некорректным.
Выходные данные
В первой строке выведите \(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)\) на момент операции не могут быть корнем.