题目描述

迷宫游戏是在一张 $n \times m$的网格图中进行的，其中 $a_{(i,j)}$ 表示第 $i$ 行、第 $j$ 列网格的状态，每个网格有以下 $4$ 种情况：

• 若$a_{(i,j)}$为. ，则表示该位置为可以走的空地
• 若$a_{(i,j)}$为# ，则表示该位置为不可走的墙壁
• 若$a_{(i,j)}$为1 ，则表示该位置为小爱初始的位置
• 若$a_{(i,j)}$为2 ，则表示该位置为小艾初始的位置

每一轮游戏开始时，可以自由决定是小爱先移动还是小艾先移动，他们可以移动至相邻的上下左右四个空格或原地不动，但又不可以移动至对方所在的网格中。

请问，游戏最少进行多少轮，才能使小爱和小艾互换位置？

输入格式

输入第一行，两个正整数分别表示 $n,m$ 接下来的第 $2$ 行至第 $n+1$ 行，每行 $m$ 个字符，其中第 $i+1$ 行、第 $j$ 列的字符表示初始时网格 $a_{(i,j)}$ 的状态。

输出格式

输出共一行，一个整数表示两人互换位置最少需要的轮数，若无法完成，则输出 No Solution。

3 3
1..
...
..2

4

样例解释 1

1.. .1. ..1 ... 2.. ... --> ... --> ... --> 2.1 --> ... ..2 .2. 2.. ... ..1

3 3
1..
###
..2

No Solution

样例解释 2

被第二行的墙挡住了

2 3
1.2
#.#

4

样例解释 3

1.2 .12 .2. 21. 2.1 #.# --> #.# --> #1# --> #.# --> #.#

3 3
1.#
#.#
#.2

No Solution

数据范围

• 对于 $50\%$的数据，$1 \leq n,m \leq 5$
• 对于 $100\%$的数据，$1 \leq n,m \leq 30$