Задачи
БинКоин
БинКоин
В компании BinCoin работает $n$ сотрудников с номерами от $1$ до $n$. Структура подчинения в этой компании представляет собой корневое дерево. Другими словами:
\begin{itemize}
\item В компании один CEO --- главный босс.
\item У каждого другого сотрудника есть ровно один непосредственный начальник.
\item В структуре подчинения нет циклов.
\end{itemize}
Более того, из-за необъяснимой любви генерального директора BinCoin ко всему бинарному, структура подчинения в компании представляет собой бинарное корневое дерево. Это означает, что каждый сотрудник является непосредственным начальником для нуля или для двух других сотрудников.
По мнению генерального директора, работать в этой компании почти так же опасно, как в шахтах. Так, сотрудники должны иногда подписывать отказ от претензий. Этот процесс происходит следующим образом. Сначала генеральный директор берет журнал и рекурсивно выполняет следующую процедуру:
Если у сотрудника, ведущего журнал, нет подчиненных, он подписывает отказ в журнале и возвращает его своему начальнику. Процедура останавливается, если это был генеральный директор, у которого нет начальника.
В противном случае
\begin{itemize}
\item они выбирают одного из двух своих прямых подчиненных равномерно случайным образом и отдают журнал одному из них;
\item когда журнал возвращается, они его подписывают;
\item потом отдают другому прямому подчиненному;
\item когда они получают журнал снова, то возвращают его своему начальнику. Процедура останавливается, если это был генеральный директор, у которого нет начальника.
\end{itemize}
Все случайные выборы независимы.
Однажды генеральный директор понял, что не может вспомнить дерево подчинения. К счастью, у них есть журнал с $k$ записями. Каждая запись представляет собой последовательность сотрудников в том порядке, в котором они подписались в журнале.
Помогите генеральному директору восстановить дерево подчинения.
\InputFile
Первая строка содержит два целых числа $n$ и $k~(1 \le n \le 999, 50 \le k \le 100)$ --- количество работников и количество записей в журнале.
Каждая из следующих $k$ строк содержит перестановку целых чисел от $1$ до $n$ --- порядок сотрудников в соответствующей записи.
Гарантируется, что входные данные были получены, как описано в постановке реальным случайным выбором.
\OutputFile
Выведите $n$ целых чисел $p_i$. Если $i$ --- генеральный директор, то $p_i$ должно быть $-1$. В противном случае $p_i$ должен быть индексом непосредственного начальника $i$-го сотрудника.
Ваш вывод должен соответствовать двоичному корневому дереву. Если входным данным удовлетворяет несколько деревьев, выведите любое из них.
Входные данные #1
3 50 1 2 3 1 2 3 3 2 1 1 2 3 3 2 1 1 2 3 1 2 3 1 2 3 1 2 3 3 2 1 1 2 3 3 2 1 1 2 3 3 2 1 1 2 3 3 2 1 1 2 3 1 2 3 3 2 1 1 2 3 3 2 1 1 2 3 3 2 1 1 2 3 1 2 3 3 2 1 1 2 3 1 2 3 1 2 3 1 2 3 3 2 1 1 2 3 3 2 1 3 2 1 1 2 3 3 2 1 1 2 3 3 2 1 3 2 1 1 2 3 1 2 3 3 2 1 1 2 3 3 2 1 3 2 1 3 2 1 1 2 3 1 2 3 3 2 1 3 2 1
Выходные данные #1
2 -1 2
Входные данные #2
5 60 2 4 3 5 1 1 5 2 4 3 1 5 2 4 3 1 5 2 4 3 1 5 3 4 2 1 5 3 4 2 1 5 3 4 2 1 5 3 4 2 1 5 3 4 2 3 4 2 5 1 2 4 3 5 1 1 5 2 4 3 3 4 2 5 1 2 4 3 5 1 2 4 3 5 1 1 5 2 4 3 3 4 2 5 1 3 4 2 5 1 1 5 2 4 3 2 4 3 5 1 1 5 2 4 3 1 5 3 4 2 3 4 2 5 1 1 5 3 4 2 1 5 2 4 3 1 5 3 4 2 1 5 2 4 3 2 4 3 5 1 2 4 3 5 1 2 4 3 5 1 2 4 3 5 1 2 4 3 5 1 1 5 2 4 3 1 5 3 4 2 1 5 2 4 3 3 4 2 5 1 1 5 3 4 2 3 4 2 5 1 3 4 2 5 1 1 5 2 4 3 2 4 3 5 1 1 5 2 4 3 1 5 3 4 2 2 4 3 5 1 2 4 3 5 1 1 5 2 4 3 1 5 2 4 3 1 5 2 4 3 1 5 2 4 3 1 5 2 4 3 3 4 2 5 1 3 4 2 5 1 3 4 2 5 1 1 5 2 4 3 1 5 3 4 2 1 5 3 4 2 2 4 3 5 1 3 4 2 5 1 1 5 2 4 3 3 4 2 5 1
Выходные данные #2
5 4 4 5 -1