\(N \times M\) 크기의 배열로 표현된 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 벽을 나타낸다.

또한, 미로에는 서로 연결된 특별한 포탈 칸이 존재할 수 있으며, 이 칸은 2로 표시된다.

당신은 (1, 1) 위치에서 출발하여 (N, M) 위치로 이동하려고 한다. 이동할 수 있는 방법은 다음과 같다.

1. 현재 칸에서 상, 하, 좌, 우로 인접한 칸(1 또는 2)으로 이동할 수 있으며, 이 때 1칸 이동하는 데 1초가 소모된다.
2. 현재 칸이 포탈(2)인 경우, 연결된 다른 포탈(2) 칸으로 순간이동할 수 있다. 순간이동을 하는 데에도 1초가 소모된다.

미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)에 도착하기까지 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

도착 지점으로 이동할 수 없는 경우에는 -1을 출력한다.

입력

첫 번째 줄에 미로의 세로 크기 \(N\)과 가로 크기 \(M\)이 공백을 사이에 두고 주어진다.

두 번째 줄부터 \(N\)개의 줄에 걸쳐 미로의 정보가 문자열로 주어진다. 각 줄은 \(M\)개의 숫자로 이루어져 있으며, 공백 없이 주어진다.

출력

(1, 1)에서 (N, M)으로 이동하는 최소 시간을 출력한다. 이동할 수 없는 경우 -1을 출력한다.

제한사항

• \(2 \le N, M \le 1,000\)
• 미로의 시작점 (1, 1)과 끝점 (N, M)은 항상 이동 가능한 칸(1)이다.
• 숫자 2(포탈)는 미로 전체에서 정확히 0개 또는 2개만 주어지며, 2개가 주어질 경우 두 포탈은 서로 연결되어 있다.

예제 입력 1

4 4
1110
1020
0000
0211

예제 출력 1

6

예제 입력 2

3 3
101
000
101

예제 출력 2

-1