던전 리모델링

이카프카의 여왕은 성에서 평화롭게 지내고 있었다. 어느 날 여왕은 다른 나라에서 많은 비밀 요원이 활동하고 있다는 소식을 듣고 성의 보안이 걱정되었다.

성에는 $h$개의 행과 $w$개의 열로 이루어진 직사각형 던전이 있다. 인접한 방은 벽으로 나뉘어 있고, 일부 벽에는 양쪽 방을 잇는 문이 있다. 입구와 출구는 던전의 대각선 방향 양 끝 모서리에 있는 두 방이다. 방들은 트리를 이룬다. 즉, 출구 방에는 모든 방에서 유일한 경로로 도달할 수 있으며, 그 경로는 각 방을 한 번씩만 지난다.

보안을 강화하려고 여왕은 트리 성질을 유지한 채 던전을 재건축하려 한다. 비용 제한 때문에 할 수 있는 일은 기존 문 하나를 막아 사용할 수 없게 만드는 것과, 어느 벽에 새 문을 하나 내는 것뿐이다. 새 문은 막은 문과 같은 벽에 낼 수도 있다.

입구에서 출구까지 이어지는 경로에 포함된 방의 수가 최대가 되도록 던전을 재건축하는 방법을 찾으시오.

첫 줄에 두 정수 $h$와 $w$가 주어진다 ($2 \le h, w \le 500$).

이어서 $(2h+1) \times (2w+1)$ 문자 격자로 던전이 주어진다. 각 문자의 의미는 다음과 같다.

• $c_{2i,2j}$는 $1 \le i \le h$, $1 \le j \le w$에 대해 .이다. $i$번째 행, $j$번째 열의 방 $(i, j)$를 나타낸다.
• $c_{2i+1,2j}$는 $1 \le i \le h-1$, $1 \le j \le w$에 대해 . 또는 -이다. 방 $(i, j)$와 $(i+1, j)$ 사이의 벽을 나타내며, .이면 문이 있고 -이면 문이 없다.
• $c_{2i,2j+1}$은 $1 \le i \le h$, $1 \le j \le w-1$에 대해 . 또는 |이다. 방 $(i, j)$와 $(i, j+1)$ 사이의 벽을 나타내며, .이면 문이 있고 |이면 문이 없다.
• $c_{1,2j}$와 $c_{2h+1,2j}$는 -이고, $c_{2i,1}$과 $c_{2i,2w+1}$은 |이다. 던전의 바깥벽이다.
• $c_{2i+1,2j+1}$은 $0 \le i \le h$, $0 \le j \le w$에 대해 +이다. 벽이나 바깥벽이 만나는 교차점이다.

입구는 방 $(1, 1)$, 출구는 방 $(h, w)$이다. 주어진 던전은 트리 성질을 만족한다.

재건축 후 입구에서 출구까지 경로 길이의 최댓값을 출력한다. 경로의 길이는 입구와 출구를 포함해 경로 위에 있는 방의 개수이다.

첫 번째 예시에서는 방 $(1, 1)$과 $(1, 2)$ 사이의 문을 막고, $(2, 1)$과 $(2, 2)$ 사이에 새 문을 내면 $(1, 1)$에서 $(2, 3)$까지의 유일한 경로가 방 6개를 모두 지난다. 이것이 분명한 최댓값이다.

두 번째 예시에서는 어떻게 재건축하더라도 $(1, 1)$에서 $(2, 3)$까지 유일한 경로의 길이가 정확히 4로 유지된다.

세 번째 예시에서 최적의 방법 중 하나는 방 $(4, 2)$와 $(4, 3)$ 사이의 문을 막고, $(2, 4)$와 $(3, 4)$ 사이에 새 문을 내는 것이다. 재건축 후의 던전은 다음과 같다.

+-+-+-+    +-+-+-+    +-+-+-+-+-+
|.|...|    |...|.|    |...|...|.|
+.+.+.+    +.+.+.+    +-+.+.+.+.+
|...|.|    |.|...|    |...|.|.|.|
+-+-+-+    +-+-+-+    +.+.+.+.+.+
                      |.|...|.|.|
                      +.+.+-+.+.+
                      |.|.|...|.|
                      +-+.+.+-+.+
                      |...|.....|
                      +-+-+-+-+-+