\(N\) коров (\(1 \leq N \leq 10^5\)), фермера Джона, пронумерованных \(1 \ldots N\),
разработали социальную иерархию, в соответствии с которой ФД доит их каждое утро.
ФД сделал \(M\) наблюдений об этой структуре (\(1 \leq M \leq 50,000\)).
Каждое наблюдение - упорядоченный список некоторых из его коров, указывающий
что их нужно доить именно в таком порядке.
Например список 2 5 1 означает, он должен подоить корову 2, некоторое время
спустя - корову 5 и некоторое время после - корову 1.
Наблюдения ФД приоритезированы, поэтому его цель - максимизировать
значение \(X\) так, чтобы выполнились условия первых \(X\) наблюдений.
Если несколько порядков дойки могут удовлетворять \(X\) наблюдениям,
он выбирает тот, в котором корова с меньшим номером доится раньше.
Иными словами, если несколько порядков дойки удовлетворяют этим
условиям, ФД выбирает лексикографически наименьший.
Порядок \(x\) является лексикографически меньшим, чем порядок \(y\), если для
некоторого \(j\), , \(x_i = y_i\) для всех \(i < j\) и \(x_j < y_j\)
(другими словами два порядка идентичны до некоторой точки, в которой
\(x\) меньше чем \(y\)).
Помогите ФД определить наилучший порядок дойки его коров.
ФОРМАТ ВВОДА (файл milkorder.in):
Первая строка содержит числа \(N\) и \(M\). Каждая из следующих \(M\) строк
описывает одно наблюдение. Строка \(i+1\) описывает наблюдение \(i\) и
начинается с количества коров \(m_i\) в этом наблюдении, за которым следует
список из \(m_i\) целых чисел, определяющих порядок коров в этом наблюдении.
Сумма \(m_i\) не превышает \(200,000\).
ФОРМАТ ВЫВОДА (файл milkorder.out):
Выведите \(N\) разделённых пробелом целых чисел дающих перестановку чисел
of \(1 \ldots N\), содержащую порядок в котором ФД должен доить своих коров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
3 1 2 3
2 4 2
3 3 4 1
|
1 4 2 3
|