#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

#define INF 99999

struct node {
  int x,y,dir,dis;
  node(){}
  node(int _x, int _y,int _dir, int _dis){
    x = _x;
    y = _y;
    dir = _dir;
    dis = _dis;
  }
  bool operator > (const node &a)const {
    return dis > a.dis;
  }
};

int mv[4][2] = {{-1,0},{0,1},{0,-1},{1,0}};
char con[35][35][35][35];
char use[35][35];
int dis[35][35];
int shm[35][35][4][35][35];
int Q[20000][2];

int x,y;


bool chk(int a,int b){
  return (0<=a && a<x && 0<=b && b<y);
}

void BFS(int sx,int sy,int dir){
  memset(use,0,sizeof(use));

  use[x-1][y-1] = 1;
  Q[0][0] = x-1;
  Q[0][1] = y-1;
  shm[sx][sy][dir][x-1][y-1] = 0;
  //if(sx==1&& sy==1)printf("sx %d sy %d dir %d\n",sx,sy,dir);

  int p,q;
  int nowX,nowY;
  int dx,dy;
  p = 0,q = -1;
  while(p!=q){
    ++q;
    nowX = Q[q][0];
    nowY = Q[q][1];


    for(int k=0;k<4;k++){
      dx = nowX + mv[k][0];
      dy = nowY + mv[k][1];
      if(chk(dx,dy) && con[nowX][nowY][dx][dy] && use[dx][dy]==0){
        use[dx][dy] = 1;
        ++p;
        Q[p][0] = dx;
        Q[p][1] = dy;
        shm[sx][sy][dir][dx][dy] = shm[sx][sy][dir][nowX][nowY]+1;
      }
    }
  }
}

int main(){
  int i,j,k;
  int dx,dy;
  int nowI;
  int tem;
  int ans;
  int nowX,nowY,nowDir,nowDis;

   while(scanf("%d%d",&x,&y)!=EOF){
    if(!(x+y))break;
    memset(con,0,sizeof(con));
    memset(use,0,sizeof(use));
    fill(&dis[0][0],&dis[34][0],INF);
    fill(&shm[0][0][0][0][0], &shm[34][0][0][0][0],INF);


    for(i=0;i+1<x+x;i++){
      nowI = i/2;
      for(j=0;j<y;j++){
        if((i%2)==0 && j==y-1)break;
        scanf("%d",&tem);
        if(i%2)con[nowI][j][nowI+1][j] = con[nowI+1][j][nowI][j] = (1-tem);
        else con[nowI][j][nowI][j+1] = con[nowI][j+1][nowI][j] = (1-tem);
      }
    }

    for(i=0;i<x;i++){
      for(j=0;j<y;j++){
        for(k=0;k<4;k++){
          dx = i + mv[k][0];
          dy = j + mv[k][1];
          if(0<=dx && dx<x && 0<=dy && dy<y){
            tem = con[i][j][dx][dy];
            con[i][j][dx][dy] = con[dx][dy][i][j] = 0;
            BFS(i,j,k);
            con[i][j][dx][dy] = con[dx][dy][i][j] = tem;
          }
        }
      }
    }

    memset(use,0,sizeof(use));
    ans = INF;
    priority_queue< node, vector< node >, greater< node > > tree;
    while(tree.empty()==false)tree.pop();
    tree.push(node(x-1, y-1, -1,0));

    while(!tree.empty()){
      node tNode = tree.top();
      tree.pop();
      if(!use[tNode.x][tNode.y]){
        nowX = tNode.x;
        nowY = tNode.y;
        nowDir = tNode.dir;

        use[nowX][nowY] = 1;

        tem = -1;
        for(int k=0;k<4;k++){
          if(chk(nowX+mv[k][0],nowY+mv[k][1]))
            tem = max(tem,shm[nowX][nowY][k][nowX][nowY]);
        }

        dis[nowX][nowY] = nowDis = max(tNode.dis,tem) ;

        //printf("nowX %d nowY %d dis %d\n",nowX,nowY,nowDis);
        if(nowX==0 && nowY==0){
          ans = nowDis;
          break;
        }
        //if(nowX==0 && nowY == 0)printf("nowDis %d\n",nowDis);

        for(int k=0;k<4;k++){
          dx = nowX + mv[k][0];
          dy = nowY + mv[k][1];
          if(chk(dx,dy)){
            //printf("dx %d dy %d k %d dis %d, shm %d\n",dx,dy, k,nowDis+1,shm[nowX][nowY][k][dx][dy]);
            //ans = min(ans, nowDis+shm[nowX][nowY][k][dx][dy]);

            //if(nowX==2 && nowY==2)printf("dx %d dy %d go %d\n",dx,dy,con[nowX][nowY][dx][dy]);
            if(con[nowX][nowY][dx][dy]&&!use[dx][dy]){
              tree.push(node(dx,dy,k,nowDis+1));
            }
          }
        }
      }
    }
    if(ans>INF)printf("-1\n");
    else printf("%d\n",ans);

   }

   return 0;
}

Measured memory_bytes: 25984