题目描述

有一个$n*m$的01矩阵，你需要从第一列的任意一个1出发，到达最后一列的任意一个1。途径的点必须为1，求最少的步数。

输入描述

第一行两个整数$n,m$，代表两个有一个n行m列的01矩阵

接下来n行，每行m个数。每个数非0即1

输出描述

输出最短步数，当不可达时输出-1。

样例

输入

3 4
0 1 1 0
1 1 1 1
0 1 0 1

输出

3