C. Симон и блоггинг
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

This life is like a TV show; we're swept along as the plotlines go.
— SHUN, TRAP

Есть $$$n$$$ блог-постов. $$$i$$$-й пост упоминает $$$l_i$$$ пользователей в порядке $$$a_i=[a_{i,1},a_{i,2},\ldots,a_{i,l_i}]$$$.

Вы собираетесь опубликовать все $$$n$$$ блогов. Будем поддерживать последовательность $$$Q$$$, которая описывает список пользователей, которых вы недавно упоминали. Вам нужно выполнить следующую операцию ровно $$$n$$$ раз:

  • Выберите неопубликованный блог $$$i$$$ ($$$1\le i\le n$$$) и опубликуйте его. Это вызовет следующие операции для каждого $$$1\le j\le l_i$$$ по порядку:
    • Если $$$a_{i,j}$$$ уже существует в $$$Q$$$, переместите $$$a_{i,j}$$$ в начало $$$Q$$$.
    • В противном случае вставьте $$$a_{i,j}$$$ в начало $$$Q$$$.

Найдите лексикографически наименьший$$$^{\text{∗}}$$$ $$$Q$$$ после всех $$$n$$$ операций.

$$$^{\text{∗}}$$$Массив $$$x$$$ лексикографически меньше массива $$$y$$$, если и только если выполняется одно из следующего:

  • $$$x$$$ — префикс $$$y$$$, но $$$x \ne y$$$; или
  • в первой позиции, где $$$x$$$ и $$$y$$$ различны, в массиве $$$x$$$ элемент меньше, чем соответствующий элемент в $$$y$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит одно целое число $$$n$$$ ($$$1\le n\le 3000$$$) — количество блогов.

Затем следуют $$$n$$$ строк, $$$i$$$-я строка начинается с целого числа $$$l_i$$$ ($$$1\le l_i\le 3000$$$), описывающего количество пользователей, упомянутых в $$$i$$$-м блоге, за которым следуют $$$l_i$$$ целых чисел $$$a_{i,1},a_{i,2},\ldots,a_{i,l_i}$$$ ($$$1\le a_{i,j}\le 10^6$$$) — список пользователей, упомянутых в $$$i$$$-м блоге.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3000$$$.

Обозначим $$$\sum\limits_{i=1}^n l_i$$$ как $$$L$$$. Гарантируется, что сумма значений $$$L$$$ по всем наборам входных данных не превосходит $$$3000$$$.

Выходные данные

Обозначим $$$m$$$ как количество пользователей, упомянутых хотя бы в одном блоге. Для каждого набора входных данных выведите $$$m$$$ целых числа $$$Q_1,Q_2,\ldots,Q_m$$$ — лексикографически наименьший $$$Q$$$.

Пример
Входные данные
5
3
5 1 2 3 4 6
3 2 5 1
4 1 9 2 3
2
2 1 6
1 6
1
3 6 1 1
5
4 2 3 3 4
5 1 2 4 3 1
2 4 1
3 3 3 1
5 4 3 2 2 2
5
4 2 3 1 4
5 2 5 5 6 5
5 3 4 7 5 5
8 3 6 4 3 1 1 5 4
2 1 1
Выходные данные
1 5 2 3 9 6 4
6 1
1 6
1 3 2 4
1 4 3 2 5 6 7
Примечание

В первом наборе входных данных вы можете публиковать блоги следующим образом:

  • Опубликуйте первый блог, и $$$Q$$$ станет $$$[6,4,3,2,1]$$$.
  • Опубликуйте третий блог, и $$$Q$$$ станет $$$[3,2,9,1,6,4]$$$.
  • Опубликуйте второй блог, и $$$Q$$$ станет $$$[1,5,2,3,9,6,4]$$$.

Существует другой способ публикации блогов:

  • Опубликуйте третий блог, и $$$Q$$$ станет $$$[3,2,9,1]$$$.
  • Опубликуйте первый блог, и $$$Q$$$ станет $$$[6,4,3,2,1,9]$$$.
  • Опубликуйте второй блог, и $$$Q$$$ станет $$$[1,5,2,6,4,3,9]$$$.

Массив $$$[1,5,2,3,9,6,4]$$$ лексикографически альтернативного варианта. Если мы не опубликуем второй блог в конце, первый элемент массива не будет $$$1$$$, поэтому $$$[1,5,2,3,9,6,4]$$$ является лексикографически наименьшим массивом $$$Q$$$.

Во втором наборе входных данных вы можете публиковать блоги следующим образом:

  • Опубликуйте первый блог, и $$$Q$$$ станет $$$[6,1]$$$.
  • Опубликуйте второй блог, и $$$Q$$$ останется $$$[6,1]$$$.

В третьем наборе входных данных вам нужно опубликовать единственный блог, и $$$Q$$$ станет $$$[1,6]$$$.