← 返回题目列表

Codeforces · 928/C

C. 依赖管理

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

Polycarp 目前正在使用 Vaja 语言开发一个项目,并使用名为 Vamen 的流行依赖管理系统。从 Vamen 的角度来看,为了简单起见,Vaja 项目和库都是经过处理的项目。

Vaja 中的项目有自己独特的非空名称,由长度不超过 10 的小写拉丁字母和版本(1 到 106 的正整数)组成。每个项目(请记住,它由名称和版本决定)可能依赖于其他项目。当然,不存在循环依赖。

您将获得一份项目描述列表。第一个项目是 Polycarp 目前正在开发的项目。帮助Polycarp确定他的项目所依赖的所有项目(直接或通过某个链)。

Polycarp 的项目可能依赖于某个项目的两个不同版本。在这种情况下,应用碰撞解决,即对于每个这样的项目,系统选择最小化其与Polycarp项目之间的距离的版本。如果有多个选项,则优先选择较新的(具有最高版本)。该版本被视为实际版本;其他版本及其依赖项将被忽略。

更正式的是,选择一组满足以下条件的尽可能最小规模的项目:

- 选择Polycarp的项目;
- Polycarp 的项目(直接或间接)依赖于该集合中的所有其他项目;
- 没有两个项目共享名称;
- 对于集合中其他项目所依赖的每个项目 x,我们有 x 或某个 y 以及其他版本和选择的 Polycarp 项目的较短链。如果出现平局,则选择较新的。

按字典顺序输出所有 Polycarp 项目的依赖项(Polycarp 项目本身不应被打印)。

输入

第一行包含一个唯一的整数 n (1 ≤ n ≤ 1 000) — Vaja 中的项目数量。

以下行包含项目描述。每个项目都由一行描述,该行由其名称和版本组成,并以空格分隔。下一行以任意顺序给出直接依赖项的数量(从 0 到 n - 1)以及依赖项本身(一行中的一个)。每个依赖项均由其名称和版本指定。这些项目也按任意顺序给出,但第一个总是波利卡普的。项目描述由一个空行分隔。请参阅示例以更好地理解。

保证不存在循环依赖。

输出

按字典顺序输出所有 Polycarp 项目的依赖项。

示例

输入 #1

4
a 3
2
b 1
c 1
b 2
0
b 1
1
b 2
c 1
1
b 2

输出 #1

2
b 1
c 1

输入 #2

9
codehorses 5
3
webfrmk 6
mashadb 1
mashadb 2
commons 2
0
mashadb 3
0
webfrmk 6
2
mashadb 3
commons 2
extra 4
1
extra 3
extra 3
0
extra 1
0
mashadb 1
1
extra 3
mashadb 2
1
extra 1

输出 #2

4
commons 2
extra 1
mashadb 2
webfrmk 6

输入 #3

3
abc 1
2
abc 3
cba 2
abc 3
0
cba 2
0

输出 #3

1
cba 2

注意

第一个示例如下图所示。从 A 到 B 的箭头表示 B 直接依赖于 A。Polycarp 的项目 «a»​​(版本 3)所依赖的项目被涂成黑色。

下图中再次给出了第二个示例。从 A 到 B 的箭头表示 B 直接依赖于 A。Polycarp 的项目 «codehorses»(版本 5)所依赖的项目将其涂成黑色。请注意,自“mashadb 1”以来,选择了“extra 1”而不是“extra 3”,并且由于“mashadb 2”,它的所有依赖项都被忽略。