Порядок доїння (Золото)
n корів фермера Джона, пронумерованих від 1 до n, встановили соціальну ієрархію, згідно з якою Джон доїть їх щоранку.
Джон зробив m спостережень щодо цієї структури. Кожне спостереження - це впорядкований список деяких з його корів, який вказує, що їх потрібно доїти саме в такому порядку. Наприклад, список 2 5 1 означає, що спочатку він повинен подоїти корову 2, потім - корову 5, а після цього - корову 1.
Спостереження Джона мають пріоритет, тому його мета - максимізувати значення X, щоб виконувалися умови перших X спостережень. Якщо кілька порядків доїння можуть задовольнити X спостереженням, він обирає той, у якому корова з меншим номером доїться раніше. Іншими словами, якщо кілька порядків доїння задовольняють цим умовам, Джон обирає лексикографічно найменший. Порядок x є лексикографічно меншим, ніж порядок y, якщо для деякого j, x[i] = y[i] для всіх i < j і x[j] < y[j] (тобто два порядки ідентичні до певної точки, в якій x менший ніж y).
Допоможіть Джону визначити найкращий порядок доїння його корів.
Вхідні дані
Перший рядок містить числа n (1 ≤ n ≤ 10^5) і m (1 ≤ m ≤ 50000). Кожен з наступних m рядків описує одне спостереження. Рядок i + 1 описує спостереження i і починається з кількості корів m[i] у цьому спостереженні, за яким слідує список з m[i] цілих чисел, що визначають порядок корів у цьому спостереженні. Сума m[i] не перевищує 200000.
Вихідні дані
Виведіть n цілих чисел, що дають перестановку чисел від 1 до n, яка містить порядок, в якому Джон повинен доїти своїх корів.
Приклад
У Джона є 4 корови, і він повинен доїти корову 1 перед коровою 2, а корову 2 перед коровою 3 (перше спостереження). Також він повинен доїти корову 4 перед коровою 2 (друге спостереження), і корову 3 перед коровою 4, а корову 4 перед коровою 1 (третє спостереження). Перші два спостереження можна задовольнити одночасно, але з третім не виходить, оскільки потрібно доїти корову 1 перед коровою 3 і корову 3 перед коровою 1.
Це означає, що є два можливих порядки: 1 4 2 3 і 4 1 2 3, з яких перший - лексикографічно найменший.