该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

时尚的小A同学设计了一张$H*W$的矩形地图，地图中每个单元格都涂成了白色或黑色。字符.代表白色，字符#代表黑色。

小A想出了一种从地图左上角走到地图右下角的方式。

每次只能向上下左右四个方向移动一格，且目标格的颜色必须与所在格的颜色不同。

小A希望尽量减少到达右下角的移动次数，但根据地图的构造，这可能无法实现。

请创建一个程序以查找最小移动次数。

格式

输入格式

第一行输入两个整数$H$ $W$,表示地图的大小

接下来 行 个字符，第 i 行 第 j 个字符表示(i,j)位置的颜色$Ai,j$

输出格式

输出一行一个整数，如果可以从左上角单元格到达右下角单元格，则输出最小移动次数，如果不可以，则输出-1。

Samples

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

9

可以考虑图中所示的操作

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

12

约束

$1\leq H\leq 500$

$1\leq W\leq 500$

$(H,W)\neq(1,1)$

数据范围