CF566A Matching Names

某编程夏令营的老师们决定给学生们一个惊喜，让他们获得风格类似于“霍比特人”电影的名字。每位学生都需要获得一个与自己的名字尽可能相似的化名。化名必须是该著名传奇中的某个角色的名字。现在老师们正忙着将化名与学生姓名进行匹配。 夏令营有 $n$ 位学生。老师们为他们恰好选择了 $n$ 个化名。每个学生必须恰好获得一个与之对应的化名。我们定义化名 $b$ 与学生名字 $a$ 的“相关度”为 $a$ 和 $b$ 最长公共前缀的长度。我们用 $\mathrm{lcp}(a, b)$ 表示该值。于是我们可以将一次假名分配的“匹配质量”定义为所有学生与相应化名的相关度之和。 请你找出一种分配方式，使得“匹配质量”最大。

第一行包含一个整数 $n$（$1 \leq n \leq 100000$），表示夏令营的学生人数。 接下来 $n$ 行，每行包含一个学生的名字。每个名字都是由小写英文字母组成的非空单词，某些名字可能会重复。 接下来的 $n$ 行，每行包含一个化名。每个化名同样是由小写英文字母组成的非空单词，某些化名可能会重复。 所有名字与化名的字符总数不超过 $800000$。

第一行输出一次最佳匹配方式下的最大总“匹配质量”。 接下来 $n$ 行，每行输出两个数字 $a\ b$（$1 \leq a, b \leq n$），表示第 $a$ 个输入学生分配到第 $b$ 个输入化名。 要求分配满足一一对应，即每个学生和每个化名只能出现一次。如果有多组最优答案，可以输出任意一组。

对于题面中的第一个示例，最佳匹配如下： - bill $→$ bilbo（lcp = 3） - galya $→$ galadriel（lcp = 3） - gennady $→$ gendalf（lcp = 3） - toshik $→$ torin（lcp = 2） - boris $→$ smaug（lcp = 0） 由 ChatGPT 5 翻译