El de la consola P18540

Jaime quiere realizar muchos comandos en su consola de Linux/Unix/Windows/Mac. Todos los comandos que tiene que ejecutar tienen la misma forma. El comando esta formado por una palabra, que es el nombre del programa, como por ejemplo cp, mv, etc. Después vienen diferentes opciones que son cadenas de texto precedidas por un guión sin espacios en medio, como -R, -verbose, etc. Por último el comando contiene la dirección de un único archivo que se referencia mediante el path relativo desde el directorio donde se está o mediante el path absoluto, como por ejemplo, /usr/bin/data.txt, oie/soluciones.pdf, ../main.cpp, etc.

Juan quiere realizar la secuencia de comandos con el mínimo número de teclas presionadas. Para ello, puede usar el comando cd para cambiar de carpeta y asi acortar los paths. Además, puede cambiar los paths absolutos por paths relativos y al revés. Juan te dice el path actual (el directorio en el que se encuentra en estos momentos) y todos los comandos que quiere ejecutar. Escribe la lista de comandos que Juan debería realizar para minimizar el número de pulsaciones que Juan debe realizar para escribirlos en su consola, contando espacios y enters.

Entrada

La entrada consisitirá en varios casos de prueba, indicándose el número de estos en la primera línea de la entrada. Cada caso empezará con una línea donde se indicará el número $M$ de comandos a ejecutar y una cadena que contendrá el path actual donde se encuentra la consula de Juan. Cada comando contendrá un nombre de comando que será una palabra formada por letras minúsculas y números, algunas opciones que serán cadenas formadas por letras minúsculas y números precedidas de un guión y el path relativo o absoluto a un archivo. El path será una cadena que contendrá letras minúsculas, números, barras y puntos. Entre los comandos a ejecutar no se encontrará ningún cd, por lo que los paths relativos indicados en la entrada siempre son relativos respecto al directorio inicial dónde se encuentra la consola de Juan

ESTA ES LA EXPLICACIÓN DE LO QUE SON LOS PATHS QUE CLARAMENTE HAY QUE MEJORAR

Un path absoluto es la dirección desde la raíz de la unidad al archivo indicando las diferentes carpetas dónde se encuentra el archivo. Un path relativo indica el camino que se ha de recorrer desde una carpeta hasta otra carpeta o un archivo, pudiendo ir hacia la carpeta padre usando ../. Por ejemplo, si estamos en la carpeta /usr/bin/ y queremos acceder al archivo hola.txt que se encuentra en la carpeta /usr/local, usaremos el path ../hola.txt, o si por ejemplo queremos movernos a la carpeta padre de la que estamos, usaremos el comando cd ../. Obsérvese que los paths absolutos empezarán por el símbolo / mientras que los relativos no. Para realizar un cambio de carpeta se puede usar el path absoluto de la carpeta o también el relativo. Los paths de las carpetas acaban en / mientras que los de los archivos acaban con el nombre del fichero, que será una secuencia de letras minúsculas y caracteres seguidos de un punto y otra secuencia de letras minúsculas y caracteres que indican el tipo del archivo.

Salida

Para cada caso de prueba se indicará el número mínimo de pulsaciones de teclado que se tiene que presionar para ejecutar todos los comandos en el mismo orden que el indicado por Juan. Los comandos se tienen que escribir de tal modo que el nombre, cada una de las opciones y el archivo estén separados por un espacio. Además, se puede ejecutar varias veces el comando cd, pero el directorio actual al acabar los comandos ha de ser el mismo que el inicial.

Solucion con DP en $O(nm)$ con $n$ el número de comandos y $m$ el número de carpetas diferentes.