รายละเอียดปัญหา

บิทาโร่ผู้รักการแต่งตัวได้ซื้อพรมผืนใหม่มา พรมมีรูปร่างเป็นสี่เหลี่ยมมุมฉากที่แบ่งออกเป็นตารางขนาดแนวตั้ง $H$ แถว และแนวนอน $W$ คอลัมน์ โดยแต่ละช่องถูกทาด้วยสีขาวหรือสีดำอย่างใดอย่างหนึ่ง สีของช่องที่อยู่ในแถวที่ $i$ จากด้านบน และคอลัมน์ที่ $j$ จากด้านซ้าย ($1 \le i \le H$, $1 \le j \le W$) ของพรม จะเป็นสีขาวเมื่ออักขระตัวที่ $j$ ของสตริง $S_i$ คือ . และเป็นสีดำเมื่อเป็น #

บิทาโร่คิดเกมขึ้นมาโดยวางหมากไว้ที่ช่องบนซ้ายสุดของพรม แล้วทำการดำเนินการต่อไปนี้ซ้ำหลายๆ ครั้ง เพื่อให้หมากนั้นไปถึงช่องล่างขวาสุดของพรม

• เลือกช่องที่อยู่ติดกันในแนวตั้งหรือแนวนอนมา $1$ ช่องที่มีสีต่างจากช่องที่หมากวางอยู่ แล้วเลื่อนหมากไปยังช่องนั้น

บิทาโร่ต้องการให้จำนวนครั้งของการดำเนินการจนกว่าจะไปถึงมีน้อยที่สุดเท่าที่จะเป็นไปได้ อย่างไรก็ตาม ขึ้นอยู่กับลวดลายของพรม ก็อาจจะไม่สามารถทำให้ไปถึงได้

เมื่อกำหนดข้อมูลลวดลายของพรมมาให้ จงเขียนโปรแกรมเพื่อตรวจสอบว่าเป็นไปได้หรือไม่ที่จะทำให้หมากไปถึงช่องล่างขวาสุดจากช่องบนซ้ายสุดด้วยการทำซ้ำการดำเนินการดังกล่าว และหากเป็นไปได้ จงหาค่าต่ำสุดของจำนวนครั้งของการดำเนินการ

ข้อจำกัด

• $1 \le H \le 500$
• $1 \le W \le 500$
• $(H, W) \neq (1, 1)$
• $S_i$ เป็นสตริงที่มีความยาว $W$ ($1 \le i \le H$)
• อักขระแต่ละตัวของ $S_i$ คือ . หรือ # ($1 \le i \le H$)
• $H, W$ เป็นจำนวนเต็ม

งานย่อย (Subtasks)

1. ($4$ คะแนน) $H = 1$
2. ($14$ คะแนน) $H \le 5$, $W \le 5$
3. ($24$ คะแนน) $H \le 30$, $W \le 30$
4. ($58$ คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ข้อมูลนำเข้า

ข้อมูลนำเข้าจะถูกกำหนดให้จากอินพุตมาตรฐานในรูปแบบต่อไปนี้

H W
S_1
S_2
:
S_H

ข้อมูลส่งออก

หากสามารถทำให้หมากไปถึงช่องล่างขวาสุดจากช่องบนซ้ายสุดได้ด้วยการทำซ้ำการดำเนินการ ให้แสดงค่าต่ำสุดของจำนวนครั้งของการดำเนินการ แต่หากเป็นไปไม่ได้ให้แสดง -1 ใน $1$ บรรทัดไปยังเอาต์พุตมาตรฐาน

ตัวอย่างข้อมูลนำเข้าและข้อมูลส่งออก

ตัวอย่างข้อมูลนำเข้า 1

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

ตัวอย่างข้อมูลส่งออก 1

9

ตัวอย่างเช่น สามารถพิจารณาการดำเนินการดังรูปได้

ในตัวอย่างด้านซ้ายสามารถไปถึงได้ด้วยการดำเนินการ $9$ ครั้ง และในตัวอย่างด้านขวาสามารถทำให้หมากไปถึงช่องล่างขวาสุดจากช่องบนซ้ายสุดได้ด้วยการดำเนินการ $13$ ครั้ง

เนื่องจากไม่สามารถไปถึงได้ด้วยจำนวนครั้งของการดำเนินการที่น้อยกว่า $9$ ครั้ง จึงแสดงผลเป็น $9$

ตัวอย่างข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของงานย่อยที่ $2, 3, 4$

ตัวอย่างข้อมูลนำเข้า 2

3 3
...
...
...

ตัวอย่างข้อมูลส่งออก 2

-1

มีกรณีที่ไม่สามารถดำเนินการได้เลยตั้งแต่แรก ในกรณีนี้ เนื่องจากไม่สามารถทำให้หมากไปถึงช่องล่างขวาสุดได้ จึงแสดงผลเป็น -1

ตัวอย่างข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของงานย่อยที่ $2, 3, 4$

ตัวอย่างข้อมูลนำเข้า 3

1 5
.#.#.

ตัวอย่างข้อมูลส่งออก 3

4

ตัวอย่างข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของงานย่อยทั้งหมด

ตัวอย่างข้อมูลนำเข้า 4

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

ตัวอย่างข้อมูลส่งออก 4

12

ตัวอย่างข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของงานย่อยที่ $2, 3, 4$

ตัวอย่างข้อมูลนำเข้า 5

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

ตัวอย่างข้อมูลส่งออก 5

12

ตัวอย่างข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของงานย่อยที่ $3, 4$