该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目：魔法石

题目描述

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

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

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

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

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

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

输入格式

第 1 行输入 2 个整数 $N, M$，表示迷宫大小。
接下来 $N$ 行，每行有 $M$ 个字符，含义如题所述。

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

输出格式

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

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

样例

样例 1

• 输入

3 4  
0000  
00A0  
A000  

• 输出

4  

样例 2

• 输入

5 4  
00AB  
0000  
0000  
1111  
0AB0  

• 输出

6  

样例 3

• 输入

4 5  
00Z00  
00101  
Z1010  
10000  

• 输出

No Solution.  

说明

样例 1 说明
哈利波特会沿着如下图所示的路线拿到魔法石。

数据范围

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