← 返回题目列表

Codeforces · 2205/C

C. 西蒙斯和发布博客

中文机器翻译题面 查看原题

人生如电视剧;随着情节的发展,我们被卷入其中。
— 顺, 陷阱

有 $$$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$$$。

示例

输入
复制

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]$$$。