Matcom Online Grader

Un día Fito leyó un artículo sobre la importancia de los sitios que acortan las urls y le llamó la atención la idea. Una aplicación de estos sitios es convertir una dirección muy larga de alguna página web, en unas pocas letras con el objetivo claro de ahorrar caracteres. Una propiedad que se intenta respetar es que no haya dos urls distintas, que se transformen en la misma cadena para así evitar colisiones.

Fito ha decidido implementar su versión del algoritmo para un problema similar. Algo que le disgusta es que con el objetivo de obtener cadenas pequeñas y únicas el resultado suele diferir mucho de la cadena original. Fito quiere mantener cierta similitud y por tanto la cadena que va a devolver, que será la que represente a la original, ha de ser una subsecuencia de esta. El objetivo principal es que la cadena sea lo más pequeña posible, pero Fito decide modificar un poco la restricción de unicidad. Para cada url que pretende reducir, va a definir otra url de control. La tarea entonces se convierte en encontrar la cadena, de menor longitud, que representa a la url original, pero no a la de control.

La primera línea de la entrada son dos enteros $n$ $ (1 \leq n \leq 1000)$ y $m$ $(1 \leq m \leq 1000)$ que indican los tamaños de ambas urls. La segunda fila contiene la url que se quiere acortar y la tercera la url de control. Ambas urls están compuestas por letras minúsculas del alfabeto latino. Se ha eliminado cualquier otro símbolo por comodidad.

La primera línea de la salida es el tamaño de la menor cadena que puede acortar a la url original y no a la de control siguiendo los deseos de Fito. La segunda línea debe mostrar la cadena que devuelve el algoritmo de Fito. Si hay varias posibles cadenas se debe imprimir la menor lexicográfica. En caso de no haber solución debe imprimir la cadena Imposible