Opis zadania

Lubiący modę Bitaro kupił nowy dywan. Dywan ma kształt prostokąta podzielonego na siatkę o $H$ wierszach w pionie i $W$ kolumnach w poziomie, a każde pole jest pomalowane na biało lub czarno. Kolor pola znajdującego się w $i$-tym wierszu od góry i $j$-tej kolumnie od lewej ($1 \le i \le H$, $1 \le j \le W$) jest biały, gdy $j$-tym znakiem napisu $S_i$ jest ., oraz czarny, gdy jest nim #.

Bitaro wymyślił zabawę polegającą na ustawieniu pionka na polu znajdującym się najbardziej na górze po lewej stronie dywanu i doprowadzeniu go na pole znajdujące się najbardziej na dole po prawej stronie poprzez kilkukrotne wykonanie następującej operacji:

• Wybierz $1$ pole o kolorze innym niż pole, na którym aktualnie stoi pionek, sąsiadujące z nim w pionie lub w poziomie, i przesuń pionek na to pole.

Bitaro chciałby, aby liczba operacji potrzebnych do dotarcia do celu była jak najmniejsza. Jednak w zależności od wzoru na dywanie dotarcie do celu może okazać się niemożliwe.

Mając dane informacje o wzorze dywanu, napisz program, który rozstrzygnie, czy powtarzając tę operację, można doprowadzić pionek z lewego górnego pola na prawe dolne pole, a jeśli jest to możliwe — wyznaczy minimalną liczbę operacji.

Ograniczenia

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ jest napisem o długości $W$ ($1 \le i \le H$).
• Każdy znak napisu $S_i$ to . lub # ($1 \le i \le H$).
• $H, W$ są liczbami całkowitymi.

Podzadania

1. ($4$ punkty) $H = 1$.
2. ($14$ punktów) $H \le 5$, $W \le 5$.
3. ($24$ punktów) $H \le 30$, $W \le 30$.
4. ($58$ punktów) Brak dodatkowych ograniczeń.

Wejście

Wejście podawane jest ze standardowego wejścia w następującym formacie:

H W
S_1
S_2
:
S_H

Wyjście

Jeśli powtarzając operację, można doprowadzić pionek z lewego górnego pola na prawe dolne pole, wypisz w $1$ wierszu na standardowe wyjście minimalną liczbę operacji; jeśli jest to niemożliwe, wypisz -1.

Przykłady

Przykład wejścia 1

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

Przykład wyjścia 1

9

Można na przykład rozważyć operacje przedstawione na rysunku.

W przykładzie po lewej stronie dotarcie pionkiem z lewego górnego pola na prawe dolne pole jest możliwe w $9$ operacjach, a w przykładzie po prawej stronie — w $13$ operacjach.

Ponieważ nie da się dotrzeć w mniej niż $9$ operacjach, wypisujemy $9$.

Ten przykład wejścia spełnia ograniczenia podzadań $2, 3, 4$.

Przykład wejścia 2

3 3
...
...
...

Przykład wyjścia 2

-1

Zdarzają się przypadki, w których od samego początku nie można wykonać żadnej operacji. W takim przypadku doprowadzenie pionka na prawe dolne pole jest niemożliwe, więc wypisujemy -1.

Ten przykład wejścia spełnia ograniczenia podzadań $2, 3, 4$.

Przykład wejścia 3

1 5
.#.#.

Przykład wyjścia 3

4

Ten przykład wejścia spełnia ograniczenia wszystkich podzadań.

Przykład wejścia 4

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

Przykład wyjścia 4

12

Ten przykład wejścia spełnia ograniczenia podzadań $2, 3, 4$.

Przykład wejścia 5

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

Przykład wyjścia 5

12

Ten przykład wejścia spełnia ograniczenia podzadań $3, 4$.