CF467D Fedor and Essay

在你帮助 Fedor 在《Call of Soldiers 3》游戏中结交朋友之后，他完全不学习了。今天，英语老师让他准备一篇作文。Fedor 不想写作文，于是找 Alex 帮忙。Alex 来帮他写好了作文，但 Fedor 一点也不喜欢这篇作文。现在 Fedor 打算用他的英文同义词词典来修改这篇作文。 Fedor 不想改变作文的意思。因此，他唯一能做的就是：将作文中的一个单词，按照词典中的替换规则，换成它的某个同义词。Fedor 可以进行任意次数的这种操作。 最终，Fedor 想要得到一篇包含尽可能少「R」字母（大小写都算）的作文。如果有多种可以使「R」数量最小的作文，他还希望作文的总长度（即所有单词长度之和）也最小。请你帮助 Fedor 得到这样一篇作文。 请注意，本题中字母大小写不敏感。例如，如果同义词词典中规定 cat 可以被替换成 DOG，那么 Cat 也可以被替换成 doG。

第一行包含一个整数 $m$（$1 \leq m \leq 10^{5}$），表示原作文的单词数。 第二行为作文的单词，单词之间用一个空格隔开。保证所有单词总长度不超过 $10^{5}$ 字母。 第三行为一个整数 $n$（$0 \leq n \leq 10^{5}$），表示同义词词典中的单词对数。 接下来的 $n$ 行，每行为两个用空格分隔的非空单词 $x_i$ 和 $y_i$，表示单词 $x_i$ 可以被替换为单词 $y_i$（但不能反向替换）。保证所有同义词对单词总长度不超过 $5 \times 10^{5}$ 字母。 所有输入中的单词都只包含英文字母（大小写均可）。

输出两个整数，分别表示在最优作文中「R」字母的最小数量，以及作文的最小总长度。

由 ChatGPT 5 翻译