Порядок доїння (Золото)#10388

Порядок доїння (Золото)

1 секунда

128 мегабайтів

Складна

Корови фермера Джона, яких, як завжди, пронумеровано від $1$ до $n$ , мають забагато вільного часу на своїх копитах. Внаслідок цього вони виробили складну соціальну ієрархію, пов'язану з порядком, у якому фермер Джон доїть їх щоранку.

Після кількох тижнів вивчення фермер Джон зробив $m$ спостережень щодо соціальної структури своїх корів. Кожне спостереження — це впорядкований список деяких корів, що означає, що цих корів слід доїти в тому самому порядку, в якому вони перераховані у списку. Наприклад, якщо одне зі спостережень фермера Джона — це список $2, 5, 1$ , то фермер Джон повинен подоїти корову $2$ в деякий момент перед коровою $5$ , а корову $5$ — в деякий момент перед коровою $1$ .

Спостереження фермера Джона мають пріоритети, тому його мета — максимізувати значення $X$ таке, що порядок доїння задовольняє умови, задані першими $X$ спостереженнями. Якщо кілька порядків доїння задовольняють ці перші $X$ умов, фермер Джон дотримується давньої традиції, згідно з якою корови з меншими номерами мають вищий ранг, ніж корови з більшими номерами, тому він хотів би доїти корів з меншими номерами першими. Точніше, якщо кілька порядків доїння задовольняють ці умови, фермер Джон хотів би використати лексикографічно найменший з них. Порядок $x$ є лексикографічно меншим за порядок $y$ , якщо існує таке $j$ , що $x_{i} = y_{i}$ x_i = y_i для всіх $i < j$ i < j та $x_{j} < y_{j}$ x_j < y_j (іншими словами, два порядки збігаються аж до деякої позиції, на якій $x$ має менший елемент, ніж $y$ ).

Допоможіть фермеру Джону визначити найкращий порядок, у якому слід доїти його корів.

Вхідні дані

Перший рядок містить два цілих числа $n$ та $m (1 \leq n \leq 1 0^{5}, 1 \leq m \leq 5 \cdot 1 0^{4})$ m~(1 \le n \le 10^5, 1 \le m \le 5 \cdot 10^4). Кожен з наступних $m$ рядків описує одне спостереження: $(i + 1)$ (i + 1)-й рядок описує спостереження $i$ і починається з числа $m_{i}$ m_i — кількості корів у спостереженні, за яким слідують $m_{i}$ m_i цілих чисел — номери цих корів у необхідному порядку. Сума всіх $m_{i}$ m_i не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Виведіть $n$ цілих чисел — перестановку чисел від $1$ до $n$ , що визначає порядок, у якому фермер Джон повинен доїти своїх корів.

Приклади

Тут у фермера Джона $4$ корови. Він повинен подоїти корову $1$ перед коровою $2$ , а корову $2$ — перед коровою $3$ (перше спостереження); корову $4$ перед коровою $2$ (друге спостереження); а також корову $3$ перед коровою $4$ , і корову $4$ перед коровою $1$ (третє спостереження). Перші два спостереження можна задовольнити одночасно, але фермер Джон не може виконати всі три одразу, оскільки це вимагало б, щоб корова $1$ йшла перед коровою $3$ , а корова $3$ — перед коровою $1$ .

Отже, існує два порядки, що задовольняють перші два спостереження: $1, 4, 2, 3$ 1, 4, 2, 3 та $4, 1, 2, 3$ 4, 1, 2, 3; перший з них є лексикографічно меншим.

Приклад 1