人行道

题目描述

小蓝住在 LQ 城，今天他要去小乔家玩。 　

LQ 城可以看成是一个 $n$ 行 $m$ 列的一个方格图。 　

小蓝家住在第 $1$ 行第 $1$ 列，小乔家住在第 $n$ 行第 $m$ 列。 　

小蓝可以在方格图内走，他不愿意走到方格图外。 　

城市中有的地方是风景优美的公园，有的地方是熙熙攘攘的街道。小蓝很喜欢公园，不喜欢街道。 他把方格图中的每一格都标注了一个属性，或者是喜欢的公园，标为 $1$，或者是不喜欢的街道标为2。小 蓝和小乔住的地方都标为了 $1$。 　

小蓝每次只能从一个方格走到同一行或同一列的相邻方格。他想找到一条路径，使得不连续走两次 标为 $2$ 的街道，请问在此前提下他最少要经过几次街道？

输入描述

输入的第一行包含两个整数 $n, m$，用一个空格分隔。 　

接下来 $n$ 行，每行一个长度为 $m$ 第数字串，表示城市的标注。　

输出描述

输出一行包含一个整数，表示答案。如果没有满足条件的方案，输出 $-1$。

输入输出样例

示例1

>输入

3 4
1121
1211
2211

>输出

2

示例2

>输入

3 4
1122
1221
2211

>输出

-1

示例3

>输入

5 6
112121
122221
221212
211122
111121

>输出

5

评测用例规模与约定

对于 $50$% 的评测用例，$2 \leq n, m \leq 20$。

对于所有评测用例，$2 \leq n, m \leq 300$。