В компании BinCoin работает сотрудников с номерами от до . Структура подчинения в этой компании представляет собой корневое дерево. Другими словами:
В компании один CEO — главный босс.
У каждого другого сотрудника есть ровно один непосредственный начальник.
В структуре подчинения нет циклов.
Более того, из-за необъяснимой любви генерального директора BinCoin ко всему бинарному, структура подчинения в компании представляет собой бинарное корневое дерево. Это означает, что каждый сотрудник является непосредственным начальником для нуля или для двух других сотрудников.
По мнению генерального директора, работать в этой компании почти так же опасно, как в шахтах. Так, сотрудники должны иногда подписывать отказ от претензий. Этот процесс происходит следующим образом. Сначала генеральный директор берет журнал и рекурсивно выполняет следующую процедуру:
Если у сотрудника, ведущего журнал, нет подчиненных, он подписывает отказ в журнале и возвращает его своему начальнику. Процедура останавливается, если это был генеральный директор, у которого нет начальника.
В противном случае
они выбирают одного из двух своих прямых подчиненных равномерно случайным образом и отдают журнал одному из них;
когда журнал возвращается, они его подписывают;
потом отдают другому прямому подчиненному;
когда они получают журнал снова, то возвращают его своему начальнику. Процедура останавливается, если это был генеральный директор, у которого нет начальника.
Все случайные выборы независимы.
Однажды генеральный директор понял, что не может вспомнить дерево подчинения. К счастью, у них есть журнал с записями. Каждая запись представляет собой последовательность сотрудников в том порядке, в котором они подписались в журнале.
Помогите генеральному директору восстановить дерево подчинения.
Первая строка содержит два целых числа и — количество работников и количество записей в журнале.
Каждая из следующих строк содержит перестановку целых чисел от до — порядок сотрудников в соответствующей записи.
Гарантируется, что входные данные были получены, как описано в постановке реальным случайным выбором.
Выведите целых чисел . Если — генеральный директор, то должно быть . В противном случае должен быть индексом непосредственного начальника -го сотрудника.
Ваш вывод должен соответствовать двоичному корневому дереву. Если входным данным удовлетворяет несколько деревьев, выведите любое из них.