Start: Mar, 15, 2024 21:00:00
20240315模拟赛
End: May, 16, 2024 01:00:00
Time elapsed:
Time remaining:

yhx 的回家之路 1586

Time Limit:  1 Sec    Memory Limit:   256 MB
Submission：50     AC：6     Score：100


Description


yhx 上夜班终于结束了！看着路边的灯光，回家这个词是如此的吸引人。

为了能够快速回家，yhx 用夺命连环call找到了大法师，希望大法师能帮他快点到家。

现在假设城市是一个 $N * M$ 的地图，yhx 公司在左上角$(1,1)$,yhx 家在右下角$(N,M)$，城市中存在一些建筑物，用 $'1'$ 表示，而能够行走的空地则用 $'0'$ 表示，yhx 只能在空地上移动，且只能上下左右移动，每次移动花费 $1$ 单位的时间

大法师为了帮助 yhx 速回家，在地图上设置了一些传送法阵，但是因为是临时设接到电话需要布置法阵，所以法师也没有仔细观察地图，就在地图上随机布置了一些法阵。

法阵用大写字母表示，当 yhx 进入 $'A'$ 传送法阵时，可以传送到另一个 $'A'$ 传送法阵（一个法阵可以使用无限次）

如果有以下地图
```
00A
000
A00
```

当 yhx 入坐标为 $(3,1)$ 的传送法阵时，会直接传送到坐标 $(1,3)$

**注意这个传送不可控，即只要进入传送法阵必须要被传送到另一边**

而如果需要从坐标为 $(1,3)$ 的传送法阵再次传送回来，则需要先移动到 $(2,3)$，再回到 $(1,3)$，重新进入法阵，才可以传送回 $(3,1)$

现在 yhx 想知道，他最快需要花费多少个单位的时间才能回到家？

若 yhx 不能回到家，则输出 "No Solution."（双引号不需要输出）

Input


输入第一行包含两个正整数 $N,M$ 表示有一个 $N * M$ 的地图

接下来 $N$ 行，每行 $M$ 个字符，题目保证输入只包含 $1,0$ 和大写字母，并且保证同一个大写字母有且只会出现两次

对于 $60\%$ 的数据，$N,M \leq 20$

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

Output

输出只有一行，该行只有一个正整数，表示 yhx 最小需要花费的时间，若无法回家则输出 "No Solution."（双引号不需要输出）

Samples

input:
3 4 0000 0000 A0A0
output:
3