问题文

縦 $H$ 行、横 $W$ 列的方格网格，左上角的格子表示为 $(1, 1)$，右下角的格子表示为 $(H, W)$。每个格子都被涂上了 $1$ 到 $9$ 中的某种颜色。

对于这个方格网格，你可以进行若干次“填充”操作。填充操作是指将从 $(1, 1)$ 开始连通的相同颜色的格子全部改成选定的颜色。两个格子相连是指它们通过共享边缘上的相同颜色的格子互相到达。以下是填充操作的示例（图像对应输入示例1）。

给定 $H \times W$ 的方格网格的初始状态，请计算使 $(1, 1)$ 和 $(H, W)$ 连通所需的最小填充操作次数。

输入

输入通过标准输入给出，具体格式如下：

$H$ $W$ $c1,1c1,2...c1,W$ $c2,1c2,2...c2,W$ : $cH,1cH,2...cH,W$

其中，$H$ 和 $W$ ($2 ≤ H, W ≤ 500$) 分别表示方格网格的高度和宽度。$ci,j$ ($1 ≤ i ≤ H, 1 ≤ j ≤ W, 1 ≤ ci,j ≤ 9$) 表示格子 $(i, j)$ 在初始状态下的颜色。

输出

输出使 $(1, 1)$ 和 $(H, W)$ 连通所需的最小填充操作次数，末尾换行。

示例1

3 3
122
131
322

输出示例1

2

将颜色 $3$ 改为颜色 $2$，则 $(1, 1)$ 和 $(3, 3)$ 连通。

示例2

3 3
111
231
321

输出示例2

0

$(1, 1)$ 和 $(3, 3)$ 最初就是连通的。

示例3

4 5
12334
41123
43214
21344

输出示例3

5