Código acm.uva.es: 10602
 El Editor Notepalo  

La compañía Macrohard ha sacado una nueva versión de su editor Notepalo, que puede entender unos pocos comandos de voz. Por ahora sólo reconoce dos comandos de voz: "repetir la última palabra" y "eliminar el último símbolo". El comando "repetir la última palabra" introduce también un espacio en blanco para separar la nueva palabra. La compañía dice que con estos comandos es posible escribir mucho más rápido, porque hay que pulsar menos teclas. Por ejemplo, una frase como "this thin thing" requiere sólo de 6 pulsaciones en el teclado.

Acción Número

de pulsaciones

Contenido del documento
Presionar "this" 4 This
Decir “repetir la última palabra” 0 this this
Decir “eliminar el último símbolo” 0 this thi
Presionar "n" 1 this thin
Decir “repetir la última palabra” 0 this thin thin
Presionar "g" 1 this thin thing

Para promocionar su editor, la compañía va a organizar un concurso en el que ganará la persona que consiga escribir un conjunto dado de palabras con el menor número de pulsaciones posible. Es más, el orden de las palabras es arbitrario, excepto la primera que siempre debe escribirse en primer lugar. Así que si las palabras son “apple”, “plum” y “apricote”, habría que escribir primero “apple” y luego las palabras “plum” y “apricote” se pueden intercambiar. Y, lo que es mejor, un buen amigo tuyo te ha dado las palabras que se van a usar en el concurso. Como quieres ganar, debes escribir un programa que encuentre el orden de las palabras que requiera un número mínimo de pulsaciones.

Entrada

La primera línea de la entrada contiene el número T de casos de prueba, entre 1 y 15. Para cada caso, la primera línea contiene el número de palabras N, entre 1 y 100. A continuación vienen N líneas, cada una con una palabra en minúsculas y no mayor de 100 letras. Recuerda que la primera palabra siempre debe ser escrita en primer lugar.

Salida

Para cada caso, la primera línea debe contener el número de pulsaciones que se deben usar para escribir todas las palabras en el editor Notepalo. Después vienen N líneas que contienen el orden de las palabras para conseguir ese mínimo. Si hay varias soluciones valdrá cualquiera de ellas.

Ejemplo de entrada Ejemplo de salida
        3
        3
        this
        thin
        thing
        4
        popcorn
        apple
        apricote
        plum
        2
        hello
        hello
        6
        this
        thin
        thing
        21
        popcorn
        plum
        apricote
        apple
        5
        hello
        hello