Tienes una palabra inicial \(a\), una palabra final \(b\) y un diccionario. Una escalera es una secuencia de palabras que empieza en \(a\) y termina en \(b\), en la que cada palabra se obtiene de la anterior cambiando exactamente una letra, y todas las palabras salvo \(a\) están en el diccionario.

Imprime la cantidad de palabras de la escalera más corta (contando \(a\) y \(b\)), o \(0\) si no hay ninguna.

Entrada

La primera línea tiene \(a\) y \(b\) \((a \ne b)\). La segunda tiene \(n\) \((1 \le n \le 5001)\) y la tercera las \(n\) palabras distintas del diccionario. Todas las palabras (incluidas \(a\) y \(b\)) tienen el mismo largo, entre \(1\) y \(10\), y son de letras minúsculas.

Salida

El largo de la escalera más corta o \(0\).

Ejemplo 1

Entrada

hit cog
6
hot dot dog lot log cog

Salida

5

Ejemplo 2

Entrada

hit cog
5
hot dot dog lot log

Salida

0

Basado en el problema 127 de LeetCode, Word Ladder, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.