题目描述

艾莉和她的同学们参加了两个学校项目。每个项目都包含全部 $N$ 名学生（包括艾莉）。

为了避免完全混乱，两位老师分别为两个项目建立了层级关系：哪个学生负责哪些学生，而这些学生又负责哪些其他学生，如此类推。

已知每个项目的层级关系都是一棵有根树，但两棵树不一定相同。例如，在一棵树中某个学生可能是所有人的负责人（根），而在另一棵树中他或她可能没有任何“下属”，也就是叶子。

学生们非常懒，想让尽可能多的人“消失”（不做任何工作）。不过，为了不在成绩册上得到坏成绩，他们必须以某种方式选择消失的人，使得两个项目仍然能够完成。

为此，在每个项目中，每个学生都给出了一个最小人数：在以他为根的原始子树（团队）中，包括他自己在内，至少需要剩下多少人，才能完成他负责的那部分项目。

可以移除没有下属的人（叶子），也可以移除有下属的人。唯一条件是：对于原始树中的每个子树，留下的人数至少要达到该子树根节点要求的人数；即使这个根节点本身被移除，也仍要满足该子树的人数限制。

现在，学生们想知道，在两个项目都仍然可以完成的前提下，最多能移除多少人。请编写程序 ditchers，找出一种可行的移除集合。

输入格式

第一行包含整数 $N$，表示学生人数。

接下来 $N$ 行，每行包含一个学生的信息，格式为：

Name: ManagerName1 Limit1 ManagerName2 Limit2

含义如下：

• 学生名为 Name；
• 在第一个项目中，他的负责人（即第一棵树中的父亲）是 ManagerName1；
• 在第一个项目中，以他为根的子树至少需要留下 Limit1 人；
• 在第二个项目中，他的负责人（即第二棵树中的父亲）是 ManagerName2；
• 在第二个项目中，以他为根的子树至少需要留下 Limit2 人。

如果某个学生是第一棵树或第二棵树的根，则对应的 ManagerName 为：

None

保证没有学生叫这个名字。

所有姓名均为大小写拉丁字母组成的字符串，不包含空格或其他字符。所有姓名长度不超过 16。

保证输入给出两棵合法的有根树。也保证在每棵树中，每个学生子树的节点数量（包括该学生自己）都不少于该学生在这棵树中要求的最小人数。

输出格式

第一行输出一个整数 $R$，表示最多可以从项目中移除的学生数量。

第二行输出 $R$ 个姓名，用空格分隔，表示要移除的学生。

如果存在多个最优解，输出任意一个即可。

数据范围

• $1 \le N \le 10000$；
• $0 \le Limit1_i,Limit2_i \le N$。

部分测试数据满足：

• 30% 的测试中，$N\le 20$；
• 60% 的测试中，$N\le 1000$。

样例

输入

8
Elly: None 4 Slavina 1
Kris: Elly 2 Stancho 0
Stancho: Elly 2 None 2
Slavina: Stancho 1 Stancho 3
Stoyan: Stancho 0 Kalina 0
Kiro: Kris 0 Stancho 1
Silvia: Stancho 0 Kiro 0
Kalina: Kris 0 Slavina 0

输出

3
Stancho Kris Silvia

样例解释

项目 1

艾莉是克里斯和斯坦乔的负责人；克里斯负责基罗和卡琳娜；斯坦乔负责西尔维娅、斯拉维娜和斯托扬。艾莉是这棵树的根，斯坦乔和克里斯是她的直接下属，处在第二层；基罗、卡琳娜、西尔维娅、斯拉维娜和斯托扬处在第三层，且都是叶子。

各学生要求如下：

• 艾莉至少需要 4 人；
• 克里斯至少需要 2 人；
• 斯坦乔至少需要 2 人；
• 基罗至少需要 0 人；
• 卡琳娜至少需要 0 人；
• 西尔维娅至少需要 0 人；
• 斯拉维娜至少需要 1 人；
• 斯托扬至少需要 0 人。

满足项目 1 限制的一种方案是移除艾莉、卡琳娜、西尔维娅和斯托扬。此时艾莉的子树中正好剩下 4 人（斯坦乔、斯拉维娜、克里斯和基罗）；克里斯和斯坦乔的子树各剩 2 人，正好满足限制；斯拉维娜子树剩 1 人，也正好满足限制；基罗子树剩 1 人，大于下界 0。

项目 2

斯坦乔负责克里斯、基罗和斯拉维娜；基罗负责西尔维娅；斯拉维娜负责艾莉和卡琳娜；卡琳娜负责斯托扬。注意，这棵树与第一个项目的树不同。

该项目中：

• 斯坦乔至少需要 2 人；
• 基罗至少需要 1 人；
• 斯拉维娜至少需要 3 人；
• 克里斯至少需要 0 人；
• 西尔维娅至少需要 0 人；
• 艾莉至少需要 1 人；
• 卡琳娜至少需要 0 人；
• 斯托扬至少需要 0 人。

满足项目 2 限制的一种方案是留下基罗、斯拉维娜、艾莉和卡琳娜，并移除其他人。

但是对于整个问题，两个单独展示的移除方案并不兼容。例如，如果采用第二个项目中的移除集合，那么在第一个项目里没有斯坦乔、西尔维娅和斯托扬时，斯坦乔子树只剩 1 人，而斯坦乔要求至少 2 人。

整个问题的一个可行最优解是移除：

Stancho Kris Silvia