Giấc mơ của Bessie

Cho mê cung $N\times M$ ô, mỗi ô có một màu:

• Đỏ (0): Không thể đi vào.
• Hồng (1): Đi vào bình thường.
• Cam (2): Đi vào bình thường; khi đi vào ô cam thì có "mùi cam" và giữ mùi này cho đến khi bị trượt trên ô tím.
• Xanh (3): Chỉ đi vào được nếu đang có mùi cam. Đi vào ô xanh không làm mất mùi cam.
• Tím (4): Khi đi vào ô tím thì bị trượt theo đúng hướng vừa đi.

Bắt đầu ở ô $(1,1)$ (góc trên trái), cần đến ô $(N,M)$ (góc dưới phải). Mỗi lần di chuyển sang một ô kề cạnh (trên, dưới, trái, phải) tính là $1$ bước.

Quy tắc trượt trên ô tím:

• Ngay khi đi vào một ô tím thì mất mùi cam (nếu đang có), và không thể dừng lại: phải đi tiếp sang ô kế tiếp theo đúng hướng đang đi. Mỗi ô trượt qua cũng tính là $1$ bước.
• Cú trượt kết thúc khi ô kế tiếp theo hướng đó không phải ô tím. Nếu ô đó đi vào được thì bước vào ô đó rồi dừng; nếu ô đó không đi vào được (ra ngoài mê cung, ô đỏ, hoặc ô xanh trong khi không có mùi cam) thì dừng ngay trên ô tím cuối cùng.
• Sau khi dừng thì lại được chọn hướng đi tùy ý như bình thường.

Hãy tìm số bước ít nhất để đến ô $(N,M)$. Nếu không thể đến được, in $-1$.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $M$.
• $N$ dòng tiếp theo: mỗi dòng $M$ số nguyên từ $0$ đến $4$ mô tả màu các ô.

Dữ liệu ra

Một số nguyên duy nhất: số bước ít nhất, hoặc $-1$ nếu không đến được.

Ràng buộc

• $1\le N,M\le 1000$
• Ô $(1,1)$ và ô $(N,M)$ luôn là hồng (1).

Ví dụ