| 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.
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.
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
|