题目描述

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$ 的最前面。

求所有 $n$ 次操作完成后，字典序最小的 $Q$。

$^{\text{∗}}$数组 $x$ 字典序小于数组 $y$，当且仅当满足下面二者之一：

• $x$ 是 $y$ 的前缀，且 $x \ne y$；
• 在 $x$ 和 $y$ 第一个不相同的位置上，$x$ 在该位置的元素更小。

输入格式

每个测试点包含多组测试用例。第一行一个整数 $t$（$1 \le t \le 1000$），代表测试用例数量。接下来是每组测试用例的描述。

第一行一个整数 $n$（$1\le n\le 3000$）——博客的数量。

接下来 $n$ 行，第 $i$ 行开头是整数 $l_i$（$1\le l_i\le 3000$），表示该博客提到的用户数量，之后跟着 $l_i$ 个整数 $a_{i,1},a_{i,2},\ldots,a_{i,l_i}$（$1\le a_{i,j}\le 10^6$）——这篇博客依次提到的用户。

保证所有测试用例的 $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$ 变为 $[6,1]$。
• 发布第二篇博客，$Q$ 保持 $[6,1]$ 不变。

第三个测试用例只有一篇博客，发布之后 $Q$ 为 $[1,6]$。

原题链接

原题链接