고장 난 문

정사각형 방들이 격자 모양으로 놓인 직사각형 미로가 있습니다. 미로의 바깥은 벽으로 둘러싸여 있고, 입구와 출구만 열려 있습니다. 입구는 가장 왼쪽 위 방의 위쪽 면이 열려 있는 곳이고, 출구는 가장 오른쪽 아래 방의 아래쪽 면이 열려 있는 곳입니다.

가로 또는 세로로 인접한 두 방 사이에는 항상 벽이 있습니다. 각 벽에는 카드 키로 여는 문이 하나 있거나, 아예 문이 없습니다. 문에 카드를 넣으면 문이 열려 지나갈 수 있지만, 문은 곧바로 다시 닫히고 넣은 카드는 돌려받지 못합니다. 어떤 카드로도 어떤 문이든 열 수 있습니다. 문이 없는 벽은 통과할 수 없습니다.

미로가 주어지면 입구에서 출구까지 가는 데 필요한 카드 수를 쉽게 계산할 수 있습니다. 지나가는 문 하나마다 카드 한 장이 듭니다. 그림 G-1의 미로에서는 그림 G-2의 초록색 화살표()를 따라가면 카드 10장으로 출구에 도달할 수 있습니다.

그림 G-1: 미로의 지도

그림 G-2: 최단 경로 중 하나

이제 문 중 정확히 하나가 고장 나 통과할 수 없다고 합시다. 다만 어느 문이 고장 났는지는 알 수 없습니다. 고장 난 문에 카드를 넣으면 카드가 곧바로 되돌아 나오고 문은 열리지 않습니다. 고장 난 문도 겉모습은 정상 문과 완전히 같아서 미리 구별할 수 없습니다.

그림 G-3: 통과하지 못할 수도 있는 미로

그림 G-3에서 빨간 X()로 표시된 문이 고장 나면 입구에서 출구로 가는 방법이 전혀 없습니다. 하지만 그림 G-1의 미로에서는 어떤 문 하나가 고장 나더라도 항상 출구에 도달할 수 있습니다. 그림 G-2의 최단 경로를 따라 출발했다가 그림 G-4에서 빨간 X로 표시된 문이 고장 났다는 것을 발견했다고 합시다. 이때 초록색 화살표를 따라가면 카드가 모두 20장 필요합니다.

그림 G-4: 문이 고장 난 미로

더 적은 카드로도 통과할 수 있습니다. 고장 난 문을 발견할 때까지 그림 G-5의 경로를 따라갑니다. 이 경로는 최단 경로가 아니어서 카드가 적어도 12장 필요하지만, 경로 위에서 고장 난 문을 찾으면 그 문을 피해 출구로 가는 최단 경로로 바꿔 갑니다. 이 전략을 쓰면 어느 문이 고장 나더라도 항상 카드 16장으로 통과할 수 있습니다. 그림 G-6은 이 전략의 최악의 경우 중 하나로, 역시 카드 16장이 필요합니다.

그림 G-5: 고장 난 문을 발견하기 전까지의 경로

그림 G-6: 이 전략의 최악의 경우 중 하나

주어진 미로에 대해, 어느 문 하나가 고장 나더라도 입구에서 출구까지 반드시 통과할 수 있도록 보장하는 최소 카드 수를 출력하는 프로그램을 작성하세요.

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

각 데이터셋의 첫 줄에는 미로의 높이 h와 너비 w가 이 순서로 두 정수로 주어집니다 (2 ≤ h, w ≤ 30). 이어지는 2 × h − 1개의 줄이 문의 위치를 나타냅니다. 이 줄들은 가로 벽과 세로 벽을 번갈아 설명합니다.

• 가로 벽을 설명하는 줄(2 × h − 1개 줄 중 1번째, 3번째, 5번째, …)은 맨 앞에 공백 하나로 시작하고, 그 뒤에 공백으로 구분된 w − 1개의 정수가 옵니다. c번째 정수는 그 행의 c번째 방과 (c+1)번째 방 사이 벽을 나타냅니다.
• 세로 벽을 설명하는 줄(2번째, 4번째, …)은 맨 앞 공백 없이 시작하고, 공백으로 구분된 w개의 정수가 옵니다. c번째 정수는 c번째 열에서 위아래로 인접한 두 방 사이 벽을 나타냅니다.

모든 경우에 정수 0은 그 벽에 문이 있음을, 1은 문이 없는 막힌 벽임을 뜻합니다.

입력의 끝은 두 개의 0으로 이루어진 줄로 표시됩니다.

각 데이터셋마다, 어느 문 하나가 고장 나더라도 출구에 도달하도록 보장하는 최소 카드 수를 정수 하나로 한 줄에 출력합니다. 어떤 문이 고장 나면 출구에 도달할 수 없게 되는 경우에는 대신 −1을 출력합니다. 그 줄에는 이 숫자 외에 다른 문자가 있어서는 안 됩니다.