题目描述

$\red{Bovidian }$船长正在拯救她的船员，$\red{Beefalo }$博士。

和所有伟大的冒险故事一样，这个故事也是发生在一个$\red{2D}$平面上的。囧

这个平面是$\red{M\times N}$的格子组成的网格，代表着船长的世界的一个侧视图。

有些格子是空的，另一些则是实心的，并且不能直接通过。

很不幸的是，船长跳不起来。她必须遵守这个世界的特殊物理法则。

$\red{1）}$如果船长的正下方没有方块（换句话说，即使她正在网格的边缘），那么她就会掉入宇宙中，同时意味着冒险失败。

$\red{2）}$如果船长的正下方的方块是空的，那么她就会掉到这个方块，

$\red{3）}$在不满足$\red{1）}$与$\red{2）}$的情况下，船长可以做一下的事情：

$\red{a) }$如果左边$\red{(}$或右边）的方格是空的，那么她可以走到那个格子。

$\red{b}$船长可以翻转重力的方向

当船长改变翻转重力的方向时，我们就改变船长"下方"的定义。

"下方"的定义只能是两种

$\red{(A)}$比船长位置所在的方格的列编号更大的格子，

$\red{(B)}$比船长位置所在的方格的列编号更小的格子,

一开始的时候，"下方"的定义是比船长位置所在方格的列编号更大的格子。

$\red{Beefalo}$博士正迷失在这个世界中的某一处，请帮助船长从起点到达博士的地方。

如果可以到达，请输出最少需要的翻转重力的次数。

如果不可以到达，请输出$\red{-1}$

输入格式

第$\red{1}$行输入两个整数 $\red{N,M}$

第$\red{2}$行到$\red{N+1}$行中，第$\red{i+1}$行则是代表船长世界的第$\red{i}$行。每行有$\red{M}$个字符。

其中","代表着一个空的格子，"#"代表着一个实心的格子，"$\red{C}$"代表着船长的位置，"$\red{D}$"代表着博士的位置。

输出格式

一行，输出一个整数。

如果船长可以到达，请输出最少需要的翻转重力的次数。

如果不可以到达，请输出$\red{-1}$

样例

输入样例

5 5
#####
#...#
#...D
#C...
##.##

输出样例

3

提示

输出解释：

首先，船长在$\red{（4,2）}$，接着她翻转重力，到达$\red{（2,2）}$

接着她向右走走到$\red{（2,4）}$，接着她第二次翻转重力，到达$\red{（4,4）}$

然后她继续向右走到$\red{（4,5）}$，最后在翻转一次重力，到达博士所在的$\red{（3,5）}$