题目描述

小$\red{S}$是一个爱锻炼的孩子，他在放假期间坚持在$\red{A}$公园练习跑步。

但不久后，他就开始为在重复的地点练习感到厌烦了，他就打算去$\red{B}$公园跑步。

但是小$\red{S}$由于没有去过$\red{B}$公园，他不知道$\red{B}$公园是否适合练习跑步，又不知道在$\red{B}$公园怎样跑是最优的。所以小$\red{S}$就去$\red{B}$公 园进行了一番勘测。

小$\red{S}$在进行了一番勘测后，画出了一张地图，地图每一个位置上都辨识了小$\red{S}$到达该位置后不能往哪一个方位移动。其中有$\red{5}$种表示的符号："$\red{U}$"代表不能向上移动，"$\red{D}$"代表不能向下移动，"$\red{L}$"代表不能向左移动，"$\red{R}$"代表不能向右移动，如果该位置有障碍物，小$\red{S}$到达那里后无法继续训练，就用"$\red{S}$"来代表。整个公园共有$\red{n}$行$\red{m}$列，小$\red{S}$会从第$\red{1}$行第$\red{1}$列出发，到第$\red{n}$行第$\red{m}$列结束他的练习。

现在小$\red{S}$想要知道，从起点（即第$\red{1}$行第$\red{1}$列）到终点（第$\red{n}$行第$\red{m}$列），途中最少要改变几次方向（即上一次移动的方向和这一次移动的方向不一样）？

注意：小$\red{S}$如在训练途中离开公园（即地图范围），则算是结束训练。

输入格式

第$\red{1}$行两个整数$\red{n}$和$\red{m，}$它们的定义请看题目描述。

第$\red{2\sim}$$\red{n+1}$行，每行有$\red{m}$个字符，表示小$\red{S}$的移动方向。

输出格式

如果小$\red{S}$从第$\red{1}$行第$\red{1}$列出发无论如何都到达不了第$\red{n}$行第$\red{m}$列，输出"$\red{No Solution}$"，否则输出小$\red{S}$途中最少要改变方向的次数。

样例

输入样例

3 3

ULL

LDU

SUD

输出样例

1

提示

样例解释

小$\red{S}$先向右移动移动了$\red{2}$格，再向下移动$\red{2}$格，就到达了终点，这样只用改变一次方向。

数据范围

$\red{10\%}$的数据是题目的馈赠。

$\red{30\%}$的数据，$\red{1≤}$$\red{n,m≤}$$\red{10}$。

$\red{50\%}$的数据，$\red{1≤}$$\red{n,m≤}$$\red{50}$。

$\red{70\%}$的数据，$\red{1≤}$$\red{n,m≤}$$\red{250}$。

$\red{100\%}$的数据，$\red{1≤}$$\red{n,m≤}$$\red{500.}$

其中$\red{50\%}$的数据是先构造出路径，再构造地图的。 $\red{100\%}$数据是随机构造的。