Migrated from Lutece 2711 魔法少女

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

身为一名魔法少女，助人为乐显然是举手之劳。

魔法少女今天又遇到了一个问题。在她手上现在正拿着一个由 $n\times m$ 个正方形元件所组成的 $n$ 行 $m$ 列 的魔法元件。每个正方形元件初始都有着2条呈对角线形状的传送门，分别对应着正方形元件的两条对角线。初始状态下，每个元件只会激活一个传送门。

现在这个元件会将左上角连接到能量输出端，右下角连到能量输入端，从第 $0$ 秒开始能量开始由输出端输出，魔法少女从第 $1$ 秒开始每秒可以施展一次魔法，将其中一个元件的传送门改变为另一条对角线对应的传送门。

现在她想知道输入端最早能在什么时候得到能量，这个问题魔法少女显然一下子就秒了，但她想考验下你能否求出答案。

Input

第 $1$ 行两个数 $n, m\ (1\le n, m \leq 500)$

如题意所示在接下来的 $n$ 行中, 每行有 $m$ 个字符。每个字符均为 \ 或 /, 表示魔法元件上魔法管道的连接方向。

Output

输出一个数, 表示所需要的最短时间。

如果永远无法得到能量，请输出 NO SOLUTION (注意输出格式)

Samples

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

1

Note

请注意时间限制并尽量优化你的算法。

Resources

2022 UESTC ICPC Training for Graph