놀라운 미로

당신은 미로 문제를 풀어야 합니다. 이 미로들을 통과하지 못하면 대회도 통과하지 못할지 모릅니다!

미로는 가로와 세로로 칸(정사각형)들이 늘어선 직사각형 영역입니다. 이 영역은 입구와 출구를 제외하고 모두 벽으로 둘러싸여 있습니다. 입구는 직사각형 윗변의 가장 왼쪽에 있습니다. 즉 가장 왼쪽 위 칸의 위쪽 변이 열려 있습니다. 출구는 같은 방식으로 아랫변의 가장 오른쪽에 있습니다. 즉 가장 오른쪽 아래 칸의 아래쪽 변이 열려 있습니다.

미로 안에서는 어떤 칸에서 가로 또는 세로로 인접한 칸으로 이동할 수 있습니다. 다만 인접한 두 칸 사이에 벽이 있을 수 있으며, 벽이 있으면 그 벽을 통과할 수 없습니다.

당신이 할 일은 입구에서 출구까지 가는 최단 경로의 길이를 구하는 것입니다. 최단 경로가 여러 개일 수도 있고, 아예 없을 수도 있습니다.

입력은 하나 이상의 데이터셋으로 이루어지며, 각 데이터셋은 하나의 미로를 나타냅니다.

각 데이터셋의 첫 줄에는 직사각형 영역의 너비 $w$와 높이 $h$가 두 정수로 순서대로 주어집니다.

그 다음 $2h - 1$개의 줄이 칸들 사이에 벽이 있는지를 설명합니다.

• 홀수 번째 줄(위에서부터 첫 번째, 세 번째, … 줄)은 한 칸의 공백으로 시작하고, 이어서 $w - 1$개의 정수가 공백으로 구분되어 주어집니다. $k$번째 정수는 같은 행에서 왼쪽으로부터 $k$번째 칸과 $k+1$번째 칸 사이(가로로 인접한 두 칸 사이)에 벽이 있는지를 나타냅니다. 이 줄들은 위에서 아래로 각각 첫 번째 행, 두 번째 행, …, $h$번째 행에 해당합니다.
• 짝수 번째 줄(두 번째, 네 번째, … 줄)은 $w$개의 정수가 공백으로 구분되어 주어집니다. $k$번째 정수는 세로로 인접한 두 행의 $k$번째 칸 사이에 벽이 있는지를 나타냅니다.

정수 $1$은 벽이 있음을, $0$은 벽이 없음을 뜻합니다.

입력의 끝은 두 개의 $0$이 적힌 줄로 표시됩니다.

데이터셋의 개수는 $100$개를 넘지 않습니다. 너비와 높이는 모두 $2$ 이상 $30$ 이하입니다.

각 데이터셋에 대해, 입구에서 출구까지의 최단 경로 길이를 정수 하나로 한 줄에 출력합니다. 경로의 길이는 지나간 칸의 개수로 정의하며, 입구 칸과 출구 칸도 함께 셉니다. 미로를 통과하는 경로가 없으면 $0$을 출력합니다. 그 줄에는 이 숫자 외의 다른 문자가 있어서는 안 됩니다.