Đảo Chiều Trọng Lực

Cho một lưới ô vuông $N\times M$ gồm các ký tự: . (ô trống), # (tường), C (vị trí xuất phát), D (vị trí đích).

Trong lưới có tác dụng của trọng lực: ban đầu trọng lực hướng xuống dưới. Nhân vật sẽ rơi theo chiều trọng lực hiện tại cho đến khi chạm vào tường hoặc biên lưới. Nếu nhân vật rơi ra ngoài biên lưới, nhiệm vụ thất bại.

Khi đang đứng trên một bề mặt (tường hoặc biên), nhân vật có thể:

• Di chuyển sang trái hoặc phải (sang ô trống kề cạnh), sau đó sẽ rơi lại theo trọng lực hiện tại.
• Đảo chiều trọng lực: trọng lực đổi chiều (từ xuống thành lên, hoặc ngược lại), sau đó nhân vật rơi theo chiều mới.

Tìm số lần đảo chiều trọng lực tối thiểu để đưa nhân vật từ C đến D.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$.
• $N$ dòng tiếp theo: Mỗi dòng gồm $M$ ký tự mô tả lưới.

Dữ liệu ra

Một số nguyên duy nhất: số lần đảo chiều trọng lực tối thiểu, hoặc $-1$ nếu không thể đến được đích.

Ràng buộc

• $1\le N,M\le 500$

Ví dụ