베시의 꿈

파머 존의 부엌에서 과일을 너무 많이 먹은 젖소 베시가 아주 이상한 꿈을 꾸고 있다. 가장 최근 꿈에서 베시는 $N \times M$ 크기의 타일 격자로 된 미로에 갇혔다 ($1 \le N, M \le 1000$). 베시는 왼쪽 위 타일에서 출발해 오른쪽 아래 타일로 가려고 한다. 어떤 타일에 서 있을 때 네 방향의 인접한 타일로 움직일 수 있다.

그런데 타일마다 색이 있고, 색마다 성질이 다르다.

• 빨간색 타일은 지나갈 수 없다.
• 분홍색 타일은 그냥 지나갈 수 있다.
• 오렌지색 타일도 그냥 지나갈 수 있고, 밟으면 베시에게서 오렌지 냄새가 난다.
• 파란색 타일에는 피라냐가 있어서, 베시에게서 오렌지 냄새가 날 때만 지나갈 수 있다.
• 보라색 타일에 들어가면 베시는 같은 방향으로 계속 미끄러지고, 보라색이 아닌 첫 타일에서 멈춘다. 미끄러지며 지나간 타일 하나하나가 한 번의 이동이다. 보라색 타일은 베시의 냄새도 없앤다.

냄새는 오렌지색 타일을 밟는 순간 생기고 보라색 타일에 들어가는 순간 사라진다. 분홍색 타일과 파란색 타일은 냄새를 바꾸지 않는다.

베시는 보라색 타일 위에서 멈출 수 없다. 미끄러지는 도중 다음 칸이 격자 밖이거나 빨간색 타일이면 그 이동은 아예 할 수 없다. 미끄러지는 동안에는 냄새가 없으므로 다음 칸이 파란색 타일일 때도 그 이동을 할 수 없다. 미끄러져 도착한 타일이 오렌지색이면 그 자리에서 다시 냄새가 난다.

베시가 왼쪽 위에서 오른쪽 아래까지 가는 데 필요한 최소 이동 횟수를 구하라.

첫째 줄에 미로의 행 개수 $N$과 열 개수 $M$이 주어진다.

다음 $N$개 줄에는 미로를 나타내는 정수가 한 줄에 $M$개씩 주어진다.

• 0은 빨간색 타일
• 1은 분홍색 타일
• 2는 오렌지색 타일
• 3은 파란색 타일
• 4는 보라색 타일

왼쪽 위와 오른쪽 아래 정수는 항상 1이다.

베시가 미로를 건너는 데 필요한 최소 이동 횟수를 한 줄에 출력한다. 건널 수 없으면 -1을 출력한다.

첫 번째 예제에서 베시는 아래로 한 칸, 오른쪽으로 두 칸 걸어간다. 두 번째 오른쪽 이동에서 보라색 타일에 올라타므로 오른쪽으로 한 칸 더 미끄러진다. 이어서 위로 한 칸, 왼쪽으로 한 칸 걸어가고, 아래로 한 칸 걸어가 보라색 타일에 올라타 아래로 두 칸 더 미끄러진다. 마지막으로 오른쪽으로 한 칸 걸어가면 도착한다. 모두 10번 움직인다 (DRRRULDDDR).