require 'set'

class Heap
	require 'forwardable'
	extend Forwardable

	def initialize
		@array = []
		@index = {}
	end

	def add(obj, key)
		@array << [obj, key]
		@index[obj] = @array.size - 1
		lift_up(@array.size - 1)
	end

	def swap(i, j)
		u = @array[i]
		v = @array[j]
		@index[u[0]], @index[v[0]] = j, i
		@array[i], @array[j] = v, u
	end

	def lift_up(i)
		return if i == 0
		j = (i - 1) / 2
		if (@array[i][1] <=> @array[j][1]) < 0
			swap(i, j)
			lift_up(j)
		end
	end

	def del_min
		raise "heap is empty!" if empty?
		min = @array[0]
		if size > 1
			swap(0, @array.size-1)
			@array.pop
			lift_down(0)
		else
			@array.pop
		end
		@index.delete(min[0])
		min
	end

	def inc_key(obj, diff)
		i = @index[obj]
		@array[i][1] += diff
		lift_down(i)
	end

	def dec_key(obj, diff)
		i = @index[obj]
		@array[i][1] -= diff
		lift_up(i)
	end

	def update_key(obj, new_key)
		i = @index[obj]
		return unless i
		return if (new_key <=> @array[i][1]) >= 0
		@array[i][1] = new_key
		lift_up(i)
	end

	def min_obj
		@array[0][0]
	end

	def min_key
		@array[0][1]
	end

	def lift_down(i)
		j = 2 * i + 1
		k = j + 1
		if k >= size
			return if j >= size
			if (@array[i][1] <=> @array[j][1]) > 0
				swap(i, j)
				lift_down(j)
			end
		else
			l = ((@array[j][1] <=> @array[k][1]) < 0 ? j : k)
			if (@array[i][1] <=> @array[l][1]) > 0
				swap(i, l)
				lift_down(l)
			end
		end
	end

	def_delegators :@array, :empty?, :size
end

def c(i, j)
	i * 32 + j
end

def dijkstra
	h = Heap.new
	s = c($h-1, $w-1)
	reached = Set[s]
	h.add(s, 0)

	dist = {}
	until h.empty?
		u, key = h.del_min
		return key if u == 0
		dist[u] = key
		$g[u].each do |v|
			e = (u < v ? [u, v] : [v, u])
			d = [$retry_dist[e][v] || -Float::INFINITY, dist[u] + 1].max
			if reached.include?(v)
				h.update_key(v, d)
			else
				h.add(v, d)
				reached << v
			end
		end
	end
end

loop do
	h, w = gets.split.map(&:to_i)
	break if h == 0
	g = {}
	(0..h-1).to_a.product((0..w-1).to_a).each do |i, j|
		g[c(i, j)] = Set.new
	end
	edges = Set.new
	h.times do |i|
		gets.split.map(&:to_i).each_with_index do |x, j|
			if x == 0
				u = c(i, j)
				v = c(i, j+1)
				edges << [u, v]
				raise if ! [1, 32].include? (u-v).abs
				g[u] << v
				g[v] << u
			end
		end

		break if i == h-1
		gets.split.map(&:to_i).each_with_index do |x, j|
			if x == 0
				u = c(i, j)
				v = c(i+1, j)
				raise if ! [1, 32].include? (u-v).abs
				edges << [u, v]
				g[u] << v
				g[v] << u
			end
		end
	end

	dist = {}
	edges.each do |e|
		u0, v0 = e
		g[u0].delete v0
		g[v0].delete u0
		s = c(h-1, w-1)
		d = {s => 0}
		queue = [s]
		until queue.empty?
			u = queue.shift
			g[u].each do |v|
				next if d[v]
				d[v] = d[u] + 1
				queue << v
			end
		end
		if !d[0]
			dist = nil
			break
		end
		dist[e] = d
		g[u0] << v0
		g[v0] << u0
	end
	
	if ! dist
		puts -1
		next
	end

	$g = g
	$retry_dist = dist
	$h = h
	$w = w

	p dijkstra
end