401436: GYM100451 E Polycarpia insolitus

Polycarpus is a well-known microbiologist, and now he breeds new varieties of bacteria. He has n bacteria of the type polycarpia ordinarius in his laboratory. For each bacterium, he knows its DNA sequence. He wants to produce new type of bacteria — polycarpia insolitus. Polycarp can obtain one new bacterium by placing two bacteria polycarpia ordinarius into one test-tube and applying specific chemical reaction. Two parental bacteria polycarpia ordinarius disappear during this process.

It is easy to see that Polycarpus can produce at most new bacteria. He knows that properties of newly created bacterium depend on the DNA sequences of two parental bacteria it was produced from. His latest researh shows that one of the most important properties, viability, is equal to the length of the longest common prefix of DNA sequences of the parental bacteria. Help him to combine polycarpia ordinarius in pairs in order to produce new bacteria with maximum total viability.

The first line contains integer n (2 ≤ n ≤ 10⁵). Each of the following n lines contains one DNA sequence of polycarpia ordinarius — non-empty string of letters 'A', 'C', 'G' and 'T'. Total length of all given sequences does not exceed 10⁶.

In the first line print the maximum total viability that can be achieved. Then print lines. Each line should contain two integers from the range [1, n] — the numbers of parental bacteria that form a pair. Bacteria of the type polycarpia ordinarius are numbered as their DNA sequences are given in the input.

4
ACAT
CAG
CC
ACGT

3
1 4
2 3

3
AC
CG
AGC

1
1 3