Deskripsi Masalah

Bitaro yang menyukai mode baru saja membeli karpet baru. Karpet tersebut berbentuk persegi panjang yang terbagi menjadi petak-petak berukuran $H$ baris secara vertikal dan $W$ kolom secara horizontal, dan setiap petak diwarnai putih atau hitam. Warna petak pada baris ke-$i$ dari atas dan kolom ke-$j$ dari kiri ($1 \le i \le H$, $1 \le j \le W$) dari karpet adalah putih apabila karakter ke-$j$ dari string $S_i$ adalah ., dan hitam apabila #.

Bitaro mendapatkan ide permainan dengan meletakkan sebuah bidak di petak paling kiri atas karpet, lalu melakukan operasi berikut beberapa kali agar bidak tersebut mencapai petak paling kanan bawah karpet:

• Pilih $1$ petak yang warnanya berbeda dengan petak tempat bidak berada saat ini serta bersebelahan secara vertikal atau horizontal, lalu pindahkan bidak ke petak tersebut.

Bitaro ingin meminimalkan banyaknya operasi hingga mencapai tujuan. Namun, bergantung pada motif karpet, bisa saja bidak tidak dapat mencapai tujuan.

Diberikan informasi mengenai motif karpet, buatlah program untuk menentukan apakah bidak dapat mencapai petak kanan bawah dari petak kiri atas dengan mengulangi operasi tersebut, dan jika mungkin, carilah banyaknya operasi minimum.

Batasan

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ adalah string dengan panjang $W$ ($1 \le i \le H$).
• Setiap karakter dari $S_i$ adalah . atau # ($1 \le i \le H$).
• $H, W$ adalah bilangan bulat.

Subsoal

1. ($4$ poin) $H = 1$.
2. ($14$ poin) $H \le 5$, $W \le 5$.
3. ($24$ poin) $H \le 30$, $W \le 30$.
4. ($58$ poin) Tidak ada batasan tambahan.

Masukan

Masukan diberikan dari masukan standar dalam format berikut:

H W
S_1
S_2
:
S_H

Keluaran

Jika bidak dapat mencapai petak kanan bawah dari petak kiri atas dengan mengulangi operasi, keluarkan banyaknya operasi minimum; jika tidak mungkin, keluarkan -1 dalam $1$ baris ke keluaran standar.

Contoh Masukan dan Keluaran

Contoh Masukan 1

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

Contoh Keluaran 1

9

Sebagai contoh, kita dapat mempertimbangkan operasi seperti pada gambar.

Pada contoh di sebelah kiri, bidak dapat mencapai petak kanan bawah dari petak kiri atas dalam $9$ kali operasi, dan pada contoh di sebelah kanan dalam $13$ kali operasi.

Karena tidak mungkin mencapainya dalam kurang dari $9$ kali operasi, keluarkan $9$.

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 4$.

Contoh Masukan 2

3 3
...
...
...

Contoh Keluaran 2

-1

Ada kalanya operasi tidak dapat dilakukan sejak awal. Dalam kasus ini, karena tidak mungkin membuat bidak mencapai petak kanan bawah, keluarkan -1.

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 4$.

Contoh Masukan 3

1 5
.#.#.

Contoh Keluaran 3

4

Contoh masukan ini memenuhi batasan semua subsoal.

Contoh Masukan 4

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

Contoh Keluaran 4

12

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 4$.

Contoh Masukan 5

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

Contoh Keluaran 5

12

Contoh masukan ini memenuhi batasan Subsoal $3, 4$.