哈利波特来到藏有魔法石的迷宫，他需要在最短的时间内拿到藏在迷宫中的魔法石。邪恶的伏地魔为了阻止他，在迷宫中设置了很多陷阱。

迷宫是一个 N \times M 的矩阵，入口在 1,1 处，魔法石藏在右下角的 N,M 处的地板下面，这个位置同时也是迷宫的出口，哈里波特走到这个点拿到魔法石就可以离开迷宫。

矩阵中的数字 0 表示这个位置是道路，可以任意走，数字 1 表示这个位置是陷阱，掉入陷阱会被困住，聪明的哈里波特会小心避开这些陷阱。从入口进入迷宫后，哈里波特要在中途不离开迷宫的前提下，用最短的时间拿到魔法石。在迷宫内，他可以沿着上下左右四方向移动，每移动一次，消耗 1 个单位的时间。

为了保护魔法石，迷宫内还有一些位置被施了魔法，成为传送门，走到一对传送门的其中一个位置，会被立刻传送到这对传送门的另一个位置，传送过程不消耗时间。

一对传送门用一对大写字母来表示，比如下图中的两个字母 A 就是一对传送门。相同字母标记的一对传送门，会唯一的出现，也就是一种大写字母，在迷宫中的出现次数只可能是 0 次或 2 次。传送门的使用不限次数。

请编程计算出，哈里波特从入口出发最短需要多长时间，可以拿到魔法石。

第 1 行输入 2 个整数 N,M，表示迷宫大小。

接下来 N 行，每行有 M 个字符，含义如题所述。

数据保证入口和出口只可能是 0，不可能是陷阱或者传送门。

输出一个整数，哈利波特拿到魔法石的最短时间。

如果哈利波特无论如何都拿不到魔法石，请输出 No Solution.。

样例 1 说明

哈里波特会沿着如下图所示的路线拿到魔法石。

数据范围

对于 100\% 的数据，1 \le N,M \le 100。

东方博宜OJ

搜索月赛