← 返回题目列表

Codeforces · 566/A

A. 匹配名称

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

一所编程暑期学校的老师决定给学生们一个惊喜,给他们起了《霍比特人》电影风格的名字。每个学生都必须有一个与自己的名字最相似的笔名。笔名肯定是流行传奇故事中某个角色的名字,现在老师们正忙着将笔名与学生的名字进行匹配。

暑期学校有 n 名学生。老师们为他们选择了n个化名。每个学生必须有一个与他准确对应的笔名。让我们将笔名 b 与姓名为 a 的学生的相关性确定为最大公共前缀 a 和 b 的长度。我们将这样的值表示为$$\operatorname{lcp}(a,b)$$。然后,我们可以将笔名与学生的匹配质量确定为所有笔名与相应学生的相关性之和。

找到学生和假名之间质量最高的匹配。

输入

第一行包含数字 n (1 ≤ n ≤ 100 000) — 暑期学校的学生人数。

接下来的 n 行包含学生的姓名。每个名称都是由小写英文字母组成的非空单词。有些名称可能会重复。

最后 n 行包含给定的假名。每个笔名都是由小英文字母组成的非空单词。有些笔名可能会重复。

所有姓名和笔名的总长度不超过800 000个字符。

输出

在第一行打印与学生匹配假名的最大可能质量。

接下来的 n 行描述了最佳匹配。每行必须采用 a b (1 ≤ a, b ≤ n) 的形式,这意味着输入中编号为 a 的学生必须与输入中编号为 b 的学生匹配。

匹配应该是一对一的对应关系,也就是说,每个学生和每个笔名应该在输出中恰好出现一次。如果有多个最优答案,则输出任意一个。

示例

输入 #1

5
gennady
galya
boris
bill
toshik
bilbo
torin
gendalf
smaug
galadriel

输出 #1

11
4 1
2 5
1 3
5 2
3 4

注意

匹配语句的第一个测试如下所示:

- bill  →  bilbo (lcp = 3)
- 加利亚 → 凯兰崔尔 (lcp = 3)
- 根纳迪  →  根道夫 (lcp = 3)
- toshik  →  torin (lcp = 2)
- 鲍里斯  →  斯毛格 (lcp = 0)