Problem Description

There is a grid with $H$ rows and $W$ columns, where the top-left cell is represented by the coordinate $(1, 1)$ and the bottom-right cell by $(H, W)$. Each cell is painted with one of the 9 colors from color $1$ to color $9$.

You can perform the "fill" operation multiple times with any of the 9 colors. The fill operation changes all cells of the same color connected to $(1, 1)$ to the selected color. Two cells are considered connected if they share an edge and are of the same color, allowing them to be reached from each other. Below is an example of the fill operation (the figure corresponds to the first input example).

Given the initial state of the $H \times W$ grid, find the minimum number of fill operations required to connect $(1, 1)$ and $(H, W)$.

Input Format

The input is provided from the standard input in the following format:

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

$H$, $W$ ($2 \leq H, W \leq 500$) represent the number of rows and columns in the grid, respectively. $c_{i,j}$ ($1 \leq i \leq H, 1 \leq j \leq W, 1 \leq c_{i,j} \leq 9$) indicates that the cell $(i, j)$ is initially painted with color $c_{i,j}$.

Output Format

Output the minimum number of fill operations required to connect $(1, 1)$ and $(H, W)$ on a single line. Ensure to include a newline at the end.

Sample Input and Output

Sample Input #1

3 3
122
131
322

Sample Output #1

2

Sample Input #2

3 3
111
231
321

Sample Output #2

0

Sample Input #3

4 5
12334
41123
43214
21344

Sample Output #3

5

Notes/Hints

Sample Explanation 1

Filling with color $3$ followed by color $2$ connects $(1, 1)$ and $(3, 3)$.

Sample Explanation 2

$(1, 1)$ and $(3, 3)$ are already connected initially.

见题面 Input 部分

见题面 Output 部分