Descripción del problema

Bitaro, amante de la moda, ha comprado una alfombra nueva. La alfombra tiene forma rectangular dividida en una cuadrícula de $H$ filas verticales y $W$ columnas horizontales, y cada casilla está pintada de color blanco o negro. El color de la casilla situada en la $i$-ésima fila desde arriba y la $j$-ésima columna desde la izquierda ($1 \le i \le H$, $1 \le j \le W$) de la alfombra es blanco cuando el $j$-ésimo carácter de la cadena $S_i$ es ., y negro cuando es #.

A Bitaro se le ocurrió un juego en el que coloca una ficha en la casilla superior izquierda de la alfombra y hace que la ficha llegue a la casilla inferior derecha realizando la siguiente operación varias veces:

• Elegir $1$ casilla que tenga un color distinto al de la casilla donde se encuentra actualmente la ficha y que sea adyacente a ella vertical u horizontalmente, y mover la ficha a esa casilla.

Bitaro quiere que el número de operaciones hasta llegar a la meta sea lo menor posible. Sin embargo, dependiendo del diseño de la alfombra, puede que no sea posible llegar.

Dada la información sobre el diseño de la alfombra, escribe un programa para determinar si es posible hacer que la ficha llegue desde la casilla superior izquierda hasta la casilla inferior derecha repitiendo la operación y, de ser posible, hallar el número mínimo de operaciones.

Restricciones

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ es una cadena de longitud $W$ ($1 \le i \le H$).
• Cada carácter de $S_i$ es . o # ($1 \le i \le H$).
• $H, W$ son números enteros.

Subtareas

1. ($4$ puntos) $H = 1$.
2. ($14$ puntos) $H \le 5$, $W \le 5$.
3. ($24$ puntos) $H \le 30$, $W \le 30$.
4. ($58$ puntos) Sin restricciones adicionales.

Entrada

La entrada se proporciona desde la entrada estándar en el siguiente formato:

H W
S_1
S_2
:
S_H

Salida

Si es posible hacer que la ficha llegue desde la casilla superior izquierda hasta la casilla inferior derecha repitiendo la operación, imprime el número mínimo de operaciones; si es imposible, imprime -1, en $1$ línea en la salida estándar.

Ejemplos de entrada y salida

Ejemplo de entrada 1

4 5
...#.
#####
...#.
#.###

Ejemplo de salida 1

9

Por ejemplo, se pueden considerar las operaciones que se muestran en la figura.

En el ejemplo de la izquierda es posible hacer que la ficha llegue desde la casilla superior izquierda hasta la casilla inferior derecha en $9$ operaciones, y en el ejemplo de la derecha en $13$ operaciones.

Como es imposible llegar en menos de $9$ operaciones, se imprime $9$.

Este ejemplo de entrada satisface las restricciones de las Subtareas $2, 3, 4$.

Ejemplo de entrada 2

3 3
...
...
...

Ejemplo de salida 2

-1

Hay casos en los que no se puede realizar ninguna operación desde el principio. En este caso, como es imposible hacer que la ficha llegue a la casilla inferior derecha, se imprime -1.

Este ejemplo de entrada satisface las restricciones de las Subtareas $2, 3, 4$.

Ejemplo de entrada 3

1 5
.#.#.

Ejemplo de salida 3

4

Este ejemplo de entrada satisface las restricciones de todas las subtareas.

Ejemplo de entrada 4

5 5
###.#
.#...
.#..#
.####
##..#

Ejemplo de salida 4

12

Este ejemplo de entrada satisface las restricciones de las Subtareas $2, 3, 4$.

Ejemplo de entrada 5

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

Ejemplo de salida 5

12

Este ejemplo de entrada satisface las restricciones de las Subtareas $3, 4$.