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