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”,它的所有依赖项都被忽略。