有 $$$n$$$ 博客。第 $$$i$$$ 个博客按数组 $$$a_i=[a_{i,1},a_{i,2},\ldots,a_{i,l_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$$$ 的开头。
- 否则,在 $$$Q$$$ 的开头插入 $$$a_{i,j}$$$。
在所有 $$$n$$$ 操作之后找到按字典顺序最小的$$$^{\text{*}}$$$ $$$Q$$$。
$$$^{\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$$$。
示例
输入复制
535 1 2 3 4 63 2 5 14 1 9 2 322 1 61 613 6 1 154 2 3 3 45 1 2 4 3 12 4 13 3 3 15 4 3 2 2 254 2 3 1 45 2 5 5 6 55 3 4 7 5 58 3 6 4 3 1 1 5 42 1 1
输出复制
1 5 2 3 9 6 46 11 61 3 2 41 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]$$$。