Thuyền trưởng Bovidian đang phiêu lưu để giải cứu thành viên trong thủy thủ đoàn của mình, Tiến sĩ Beefalo. Giống như mọi cuộc phiêu lưu vĩ đại, câu chuyện này diễn ra trên một lưới hai chiều \(N \times M\) (\(1 \le N, M \le 500\)), biểu diễn góc nhìn từ bên hông thế giới của thuyền trưởng. Một số ô lưới trống, còn những ô khác bị chặn và không thể đi qua.

Không may, Thuyền trưởng Bovidian không thể nhảy. Cô phải tuân theo các quy luật vật lý sau khi di chuyển trong thế giới của mình:

1. Nếu không có ô nào ngay bên dưới Thuyền trưởng Bovidian (nghĩa là nếu cô đang ở mép lưới), cô sẽ bay ra ngoài không gian và thất bại trong nhiệm vụ.
2. Nếu ô ngay bên dưới Thuyền trưởng Bovidian trống, cô sẽ rơi vào ô đó.
3. Nếu không:
   • a) Thuyền trưởng Bovidian có thể di chuyển sang trái hoặc sang phải nếu ô tương ứng tồn tại và trống.
   • b) Hoặc Thuyền trưởng Bovidian có thể đảo chiều trọng lực.

Khi Thuyền trưởng Bovidian đổi chiều trọng lực, ô “bên dưới” cô (như được nhắc đến trong quy tắc 1 và 2) chuyển đổi qua lại giữa ô có chỉ số hàng lớn hơn một và ô có chỉ số hàng nhỏ hơn một (hàng đầu tiên trong dữ liệu vào có chỉ số 1 và hàng cuối cùng có chỉ số \(N\)). Ban đầu, các ô có chỉ số hàng lớn hơn một nằm bên dưới Thuyền trưởng Bovidian.

Tiến sĩ Beefalo bị lạc đâu đó trong thế giới này. Hãy giúp Thuyền trưởng Bovidian đến ô của cô ấy với số lần đảo chiều trọng lực ít nhất có thể. Nếu không thể đến được chỗ Tiến sĩ Beefalo, hãy in ra -1.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(M\), cách nhau bởi một dấu cách.
• Các dòng từ 2 đến \(1+N\): dòng \(i+1\) mô tả hàng thứ \(i\) trong thế giới của Thuyền trưởng Bovidian; . biểu thị một ô trống, # biểu thị một ô bị chặn, C biểu thị vị trí ban đầu của Thuyền trưởng Bovidian và D biểu thị vị trí ban đầu của Tiến sĩ Beefalo.

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất là số lần ít nhất Thuyền trưởng Bovidian phải đảo chiều trọng lực để đến chỗ Tiến sĩ Beefalo, hoặc -1 nếu không thể đến chỗ Tiến sĩ Beefalo.

Ví dụ

5 5
#####
#...#
#...D
#C...
##.##

3

Nguồn

USACO 2013 US Open, Silver — Problem 1: What's Up With Gravity

Tác giả đề: Mark Gordon, 2013.