Problem B: 迷図と命ず

日本語では「迷路」と呼ぶことが多い maze だが，英語と発音を似せて「迷図」 と呼ぶ人もいる．迷図を通り抜けられないようでは，国内予選を通過するのも 難しいかも!

この問題の迷図は，四角を縦横に並べた長方形の領域である．この領域は出入 口を除いて壁で囲まれている．迷図の入口は長方形の上辺の最も左側で，つま り最上段の最左の四角の上辺は開いている．出口は同様に下辺の最も右側にあ る．

迷図の中では縦または横に隣り合う四角に行くことができる．しかし隣とは壁 で隔てられていることがあり，その場合直接には行き来できない．

あなたの仕事は，入口から出口までの最短経路の長さを求めることである．最 短経路が複数あることもあれば，ひとつもないこともあるのに注意されたい．

Input

入力はそれぞれが迷図を表すひとつ以上のデータセットからなる．

データセットの最初の行には迷図の幅 w と高さ h を与えるふ たつの整数値がこの順に入っている．

それに続く 2 × h − 1 行は，隣接する四角の間の壁の 有無を示している．最初の行の先頭は空白で，その後には w − 1 個の 1 または 0 が空白ひとつで区切られて並んでいる．これらは一番上の行 の横に隣り合う四角の間の壁の有無を示すものである．1 は壁があることを， 0 はないことを意味する． 次の行の先頭には空白はなく，w 個の 1 または 0 が空白ひとつを区切りに続く．これらは最初と次の行の縦に隣り合う 四角の間の壁の有無を表す．整数 1/0 は壁の有/無を示す．引き続く行は交互 に横と縦に隣り合う四角の間の壁の有無を同様に表す．

入力の終わりは二つのゼロを含む行で表される．

データセット数は100以下である．長方形領域の高さも幅も2以上30以下であ る．

Output

各データセットについて，入口から出口までの最短経路長を表す整数ひとつを 持つ行を出力せよ．ここでは経路の長さは通過する四角の数で表す．迷図を通 り抜ける経路がない場合には，ゼロひとつを含む行を出力せよ．出力行にはこ の数値以外の文字を含んではならない．

Sample Input

2 3
 1
0 1
 0
1 0
 1
9 4
 1 0 1 0 0 0 0 0
0 1 1 0 1 1 0 0 0
 1 0 1 1 0 0 0 0
0 0 0 0 0 0 0 1 1
 0 0 0 1 0 0 1 1
0 0 0 0 1 1 0 0 0
 0 0 0 0 0 0 1 0
12 5
 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0
 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0
 0 0 1 0 0 1 0 1 0 0 0
0 0 0 1 1 0 1 1 0 1 1 0
 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 0 0
0 0

Output for the Sample Input

4
0
20

---