問題文

前回の門松列の傾向と対策問題で、出そうと思っていた門松列問題を当てられたので万事休すかとおもいきや、１次元列を離れ２次元グリッドに飛び出す事になりました。

ここ最近何度も出てますが「門松列」とは、「3つの竹の長さの降順で2番目が、左または右側になっているもの」、「3つの長さはすべて異なる」という条件を満たすものである。

ここで、$W\times H$の平面グリッドで各マスは$1$から$9$の数値が書かれたマスが与えられます。
それらのマスを現在地から1ステップごとに上下左右1マス（マンハッタン距離1)だけ進むことができます。
ただし、直近2回のいた場所と新しいマスの数値の順番が、門松列をなしてなければなりません。

つまり、 $A$を到達したマスの数値の履歴として$A_i$を$i$番目に通ったマスの数値とし、
$isKadomatsuSequence$を門松列かどうか判定する関数だとすると。

$isKadomatsuSequence(A_{i-2},A_{i-1},A_i)$

入力

$W$ $H$
$M_{1,1}{M}_{2,1}\dots M_{W,1}$
$M_{1,2}{M}_{2,2}\dots M_{W,2}$
$\dots \dots \dots \dots \dots \dots$
$M_{1,H}{M}_{2,H}\dots M_{W,H}$

入力は全て整数で与えられる。
$2\le W\le 100={10}^2$
$2\le H\le 100={10}^2$
$1\le M_{i,j}\le 9$
$1\le i\le W,1\le j\le H$

出力

スタート地点からゴール地点にたどり着くまでの最短ステップ数を求めてください。
この条件でゴールできなければ -1を出力してください。
最後に改行をしてください。

サンプル

3 3
1 2 3
3 2 1
1 4 1

4

2 2
1 3
2 2

2

4 4
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

-1

3 3
5 4 1
6 6 9
2 8 8

6