#include <iostream>
#include <queue>
using namespace std;

//#define DEBUG
#define MAX_H 30
#define MAX_W 30
#define MAP_H (MAX_H * 2 - 1)
#define MAP_W (MAX_W * 2 - 1)

#define T 100000
#define U -10
#define D -20
#define L -30
#define R -40

typedef struct _point { // show map[y][x];
	int x;
	int y;
} P;

typedef struct _pair {
	int cost;
	P point;
} Pair;

int H, W;
int **MAP, **tmpMAP;

void setTO(int **map, P p, int val) {
//	if (map[p.y][p.x] == U) {
//		map[p.y - 1][p.x] = val;
//	} else if (map[p.y][p.x] == D) {
//		map[p.y + 1][p.x] = val;
//	} else if (map[p.y][p.x] == L) {
//		map[p.y][p.x - 1] = val;
//	} else if (map[p.y][p.x] == R) {
//		map[p.y][p.x + 1] = val;
//	} //else
	map[p.y][p.x] = val;
	return;
}

void closeDoor(int **map, P p) {
	setTO(map, p, T);
}
void openDoor(int **map, P p) {
	setTO(map, p, 0);
}
void refreshMap(int **map) {
	for (int y = 0; y < 2 * H - 1; y++) {
		if (y % 2 != 0) continue;
		for (int x = 0; x < 2 * W - 1; x++) {
			if (x % 2 != 0) continue;
			map[y][x] = 0;
		}
	}
}

bool judgeAll(int i, int k) {
	//cout << "fuga" << endl;
	return i == 0;
}

bool judgeOnly(int i, int k) {
	//cout << "fuga" << endl;
	return !(i == 1 || i == T || i == k);
}

int route(int **map, P start, P goal, int k, bool useall) {
	//cout << "??????????????????" << endl;
	bool (*judge)(int, int);
	if (useall) judge = judgeAll;
	else        judge = judgeOnly;
	queue < Pair > que;
	refreshMap(map);
	Pair pair;
	P p = start;
	//p.x = 0;
	//p.y = 0;
	pair.cost = 0;
	pair.point = p;
	que.push(pair);
	map[p.y][p.x] = -1;
	while (!que.empty()) {
		//cout << "hoge" << endl;
		pair = que.front();
		que.pop();
		//cout << pair.point.y << "<>" << pair.point.x << endl;
		if (pair.point.x == goal.x && pair.point.y == goal.y) return pair.cost;
		//cout << "hoge2" << endl;
		// UP
		if (pair.point.y - 2 >= 0 &&
			judge(map[pair.point.y - 1][pair.point.x], k) &&
			map[pair.point.y - 2][pair.point.x] == 0
		) {
			//cout << "fooU" << endl;
			Pair npair;
			P pp = pair.point;
			pp.y -= 2;
		//cout << pp.y << "<**>" << pp.x << endl;
			npair.cost = pair.cost + 1;
			npair.point = pp;
			que.push(npair);
			map[pp.y][pp.x] = D;
		}
		//cout << "hoge3" << endl;
		// DOWN
		if (pair.point.y + 2 < 2 * H - 1 &&
			judge(map[pair.point.y + 1][pair.point.x], k) &&
			map[pair.point.y + 2][pair.point.x] == 0
		) {
			//cout << "foo" << endl;
			Pair npair;
			P pp = pair.point;
			pp.y += 2;
		//cout << pp.y << "<**>" << pp.x << endl;
			npair.cost = pair.cost + 1;
			npair.point = pp;
			que.push(npair);
			map[pp.y][pp.x] = U;
		}
		//cout << "hoge4" << endl;
		// LEFT
		if (pair.point.x - 2 >= 0 &&
			judge(map[pair.point.y][pair.point.x - 1], k) &&
			map[pair.point.y][pair.point.x - 2] == 0
		) {
			Pair npair;
			P pp = pair.point;
			pp.x -= 2;
		//cout << pp.y << "<**>" << pp.x << endl;
			npair.cost = pair.cost + 1;
			npair.point = pp;
			que.push(npair);
			map[pp.y][pp.x] = R;
		}
		//cout << "hoge5" << endl;
		// RIGHT
		if (pair.point.x + 2 < 2 * W - 1 &&
			judge(map[pair.point.y][pair.point.x + 1], k) &&
			map[pair.point.y][pair.point.x + 2] == 0
		) {
			Pair npair;
			P pp = pair.point;
			pp.x += 2;
		//cout << pp.y << "<**>" << pp.x << endl;
			npair.cost = pair.cost + 1;
			npair.point = pp;
			que.push(npair);
			map[pp.y][pp.x] = L;
		}
	}
	
	return -1;
}

void cp2(int **dst, int **map) {
	for (int y = 0; y < 2 * H - 1; y++) {
		if (y % 2 != 0) continue;
		for (int x = 0; x < 2 * W - 1; x++) {
			if (x % 2 != 0) continue;
			dst[y][x] = map[y][x];
		}
	}
}

void solve() {
	int maxx = 100000;
	P start, goal;
	start.x = 0;
	start.y = 0;
	goal.y = 2 * H - 2;
	goal.x = 2 * W - 2;
	int t;
	bool first = true;
	for (int k = 2; (t = route(MAP, start, goal, k, true)) != -1; k++) {
		int badest = 0;
		P badp;
		P now = goal;
		for (int i = t - 1; i >= 1; i--) {
			cp2(tmpMAP, MAP);
			P tnow = now;
			if (MAP[now.y][now.x] == U) {
				now.y -= 2;
				tnow.y -= 1;
				closeDoor(tmpMAP, tnow);
			} else if (MAP[now.y][now.x] == D) {
				now.y += 2;
				tnow.y += 1;
				closeDoor(tmpMAP, tnow);
			} else if (MAP[now.y][now.x] == L) {
				now.x -= 2;
				tnow.x -= 1;
				closeDoor(tmpMAP, tnow);
			} else if (MAP[now.y][now.x] == R) {
				now.x += 2;
				tnow.x += 1;
				closeDoor(tmpMAP, tnow);
			}
			int l = route(tmpMAP, now, goal, k, false);
			if (first && l == -1) {
				cout << -1 << endl;
				return;
			}
			if (badest < i + l) {
				badp = tnow;
				badest = i + l;
			}
			openDoor(tmpMAP, tnow);
		}
		setTO(MAP, badp, k);
#ifdef DEBUG
		for (int y = 0; y < 2 * H - 1; y++) {
			//if (y % 2 != 0) continue;
			for (int x = 0; x < 2 * W - 1; x++) {
				//if (x % 2 != 0) continue;
				cout << MAP[y][x] << "\t";
			}
			cout << endl;
		}
		cout << endl;
#endif
		if (maxx > badest) maxx = badest;
		first = false;
	}
	cout << maxx << endl;
}

int main(void) {
	MAP = new int*[MAP_H];
	tmpMAP = new int*[MAP_H];
	for (int i = 0; i < MAP_H; i++) {
		MAP[i] = new int[MAP_W];
		tmpMAP[i] = new int[MAP_W];
		for (int j = 0; j < MAP_W; j++) {
			MAP[i][j] = 0;
			tmpMAP[i][j] = 0;
		}
	}

	cin >> H >> W;
	while (H != 0 && W != 0) {
		for (int y = 0; y < 2 * H - 1; y++) {
			for (int x = 0; x < 2 * W - 1; x++) {
				int k = 0;
				if ((x + y) % 2 != 0) cin >> k;
				MAP[y][x] = tmpMAP[y][x] = k;
			}
		}
		solve();
		//cout << endl;
		cin >> H >> W;
	}
}

Measured memory_bytes: 1244