题目描述

译自 BalticOI 2011 Day1 T3「Switch the Lamp On」

有一种正方形的电路元件，在它的两组相对顶点中，有一组会用导线连接起来，另一组则不会。

有 $N\times M$ 个这样的元件，你想将其排列成 $N$ 行 $M$ 列放在电路板上。电路板的左上角连接电源，右下角连接灯泡。 试求：至少要旋转多少个正方形元件才能让电源与灯泡连通，若无解则输出 $\texttt{NO SOLUTION}$。

输入格式

第一行有两个整数 $N$ 和 $M$。

在接下来的 $N$ 行中，每行有 $M$ 个字符。每个字符均为 \ 或 /，表示正方形元件上导线的连接方向。

输出格式

输出共一行，若有解则输出一个整数，表示至少要旋转多少个正方形元件才能让电源与灯泡连通；若无解则输出 NO SOLUTION。

样例

输入

3 5
\\/\\
\\///
/\\\\

输出

1

数据范围与提示

对于 $40\%$ 的数据，$1 \leq N \leq 4$，$1 \leq M \leq 5$。

对于所有数据，$1 \leq N,M \leq 500$。