Matching Names

题意翻译

一个学校里有n个学生，同时有n个笔名。每个学生选一个笔名，找出一种配对方法，使得每个真名与笔名之间的最大公共前缀长度之和最大（n<=1e5）。 如：bill与bilbo的最大公共前缀长为3（前缀bil），galya与 galadriel的最大公共前缀长为3（前缀gal）等。

题目描述

Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the "Hobbit" movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names. There are $ n $ students in a summer school. Teachers chose exactly $ n $ pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym $ b $ to a student with name $ a $ as the length of the largest common prefix $ a $ and $ b $ . We will represent such value as . Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students. Find the matching between students and pseudonyms with the maximum quality.

输入输出格式

输入格式

The first line contains number $ n $ ( $ 1<=n<=100000 $ ) — the number of students in the summer school. Next $ n $ lines contain the name of the students. Each name is a non-empty word consisting of lowercase English letters. Some names can be repeating. The last $ n $ lines contain the given pseudonyms. Each pseudonym is a non-empty word consisting of small English letters. Some pseudonyms can be repeating. The total length of all the names and pseudonyms doesn't exceed $ 800000 $ characters.

输出格式

In the first line print the maximum possible quality of matching pseudonyms to students. In the next $ n $ lines describe the optimal matching. Each line must have the form $ a $ $ b $ ( $ 1<=a,b<=n $ ), that means that the student who was number $ a $ in the input, must match to the pseudonym number $ b $ in the input. The matching should be a one-to-one correspondence, that is, each student and each pseudonym should occur exactly once in your output. If there are several optimal answers, output any.

输入输出样例

输入样例 #1

5
gennady
galya
boris
bill
toshik
bilbo
torin
gendalf
smaug
galadriel

输出样例 #1

11
4 1
2 5
1 3
5 2
3 4

说明

The first test from the statement the match looks as follows: - bill $ → $ bilbo (lcp = 3) - galya $ → $ galadriel (lcp = 3) - gennady $ → $ gendalf (lcp = 3) - toshik $ → $ torin (lcp = 2) - boris $ → $ smaug (lcp = 0)