Bitaro thích những đồ vật đẹp và vừa mua một tấm thảm mới. Tấm thảm có hình chữ nhật, được chia thành \(H\) hàng và \(W\) cột ô vuông. Mỗi ô được tô màu trắng hoặc đen. Ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang (\(1 \le i \le H\), \(1 \le j \le W\)) có màu trắng nếu ký tự thứ \(j\) của xâu \(S_i\) là ., và có màu đen nếu ký tự đó là #.

Bitaro nghĩ ra một trò chơi: đặt một quân cờ ở ô trên cùng bên trái của tấm thảm, rồi thực hiện thao tác sau một số lần để đưa quân cờ đến ô dưới cùng bên phải:

• Chọn một ô có màu khác với ô quân cờ đang đứng và kề với ô đó theo một trong bốn hướng trên, dưới, trái, phải; sau đó chuyển quân cờ sang ô đã chọn.

Bitaro muốn thực hiện ít thao tác nhất có thể. Tuy nhiên, tùy theo hoa văn của tấm thảm, có thể không đưa được quân cờ đến đích.

Cho hoa văn của tấm thảm, hãy xác định liệu có thể đưa quân cờ từ ô trên cùng bên trái đến ô dưới cùng bên phải bằng cách lặp lại thao tác trên hay không. Nếu có thể, hãy tìm số thao tác ít nhất.

Dữ liệu vào

Dữ liệu vào có dạng:

H W
S_1
S_2
...
S_H

Dữ liệu ra

In ra một dòng chứa số thao tác ít nhất nếu có thể đưa quân cờ từ ô trên cùng bên trái đến ô dưới cùng bên phải. Nếu không thể, in ra \(-1\).

Ràng buộc

• \(1 \le H \le 500\).
• \(1 \le W \le 500\).
• \((H,W) \ne (1,1)\).
• \(S_i\) là xâu có độ dài \(W\) (\(1 \le i \le H\)).
• Mỗi ký tự của \(S_i\) là . hoặc # (\(1 \le i \le H\)).
• \(H,W\) là các số nguyên.

Phân nhóm

1. 4 điểm: \(H=1\).
2. 14 điểm: \(H \le 5\), \(W \le 5\).
3. 24 điểm: \(H \le 30\), \(W \le 30\).
4. 58 điểm: Không có ràng buộc bổ sung.

Ví dụ

4 5
...#.
#####
...#.
#.###

9

3 3
...
...
...

-1

1 5
.#.#.

4

5 5
###.#
.#...
.#..#
.####
##..#

12

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

12

Nguồn

Đề bài Carpet, JOI 2021/2022, vòng loại thứ hai, bài 2 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.