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 ≤ 100 000) — 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 800 000 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 ab (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<br />gennady<br />galya<br />boris<br />bill<br />toshik<br />bilbo<br />torin<br />gendalf<br />smaug<br />galadriel<br />
输出
11<br />4 1<br />2 5<br />1 3<br />5 2<br />3 4<br />
备注:
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)
加载中...