题目描述

Icpca 的女王平静地居住在一座城堡中。一天，她听说许多特工在其他国家活跃，于是开始担忧城堡的安全。

城堡有一个矩形地牢，由 $h$ 行 $w$ 列的正方形房间组成。相邻房间由墙壁隔开。有些墙壁上有门道，使得被隔开的房间可以互通。地牢的入口和出口位于两个对角线的角落房间。地牢的房间构成一棵 树，也就是说，从地牢的每个房间到出口房间都有一条唯一的路径可达，该路径上的每个房间仅经过一次。

为了增强城堡的安全，女王想要改造地牢，使得从入口房间到出口房间的路径上的房间数量最大化。她喜欢当前地牢的树状属性，因此必须保留这一特性。由于成本限制，改造只能做两件事：封闭一个现有的门道使其不可用，并在另一面墙（可能是同一面墙）上建造一个新的门道。

你的任务是找到一种改造地牢的方法，以满足女王的需求。

输入格式

输入由单个测试用例组成，格式如下。

$h$ 和 $w$ 表示地牢的大小，每个都是介于 $2$ 到 $500$ 之间（含）的整数。字符 $c_{i,j}$ ($1 \leq i \leq 2h+1$, $1 \leq j \leq 2w+1$) 表示地牢的配置，如下所示：

• $c_{2i,2j} = \text{'}.\text{'}$ 对于 $1 \leq i \leq h$ 和 $1 \leq j \leq w$，对应地牢中从北端数第 $i$ 行、西端数第 $j$ 列的房间；这样的房间称为房间 $(i,j)$。
• $c_{2i+1,2j} = \text{'}.\text{'}$ 或 $\text{'}-\text{'}$ 对于 $1 \leq i \leq h-1$ 和 $1 \leq j \leq w$，表示房间 $(i,j)$ 和 $(i+1,j)$ 之间的墙壁；字符 $\text{'}.\text{'}$ 表示该墙有门道，$\text{'}-\text{'}$ 表示没有门道。
• $c_{2i,2j+1} = \text{'}.\text{'}$ 或 $\text{'}|\text{'}$ 对于 $1 \leq i \leq h$ 和 $1 \leq j \leq w-1$，表示房间 $(i,j)$ 和 $(i,j+1)$ 之间的墙壁；字符 $\text{'}.\text{'}$ 表示该墙有门道，$\text{'}|\text{'}$ 表示没有门道。
• $c_{1,2j} = c_{2h+1,2j} = \text{'}-\text{'}$ ($1 \leq j \leq w$) 和 $c_{2i,1} = c_{2i,2w+1} = \text{'}|\text{'}$ ($1 \leq i \leq h$)，对应地牢的外墙。
• $c_{2i+1,2j+1} = \text{'}+\text{'}$ 对于 $0 \leq i \leq h$ 和 $0 \leq j \leq w$，对应墙壁或外墙的交点。

地牢的入口和出口分别位于房间 $(1,1)$ 和 $(h,w)$。配置满足上述的树状属性。

输出格式

输出通过改造可以达到的从入口房间到出口房间的路径的最大长度，其中路径长度是经过的房间数量，包括入口和出口房间。

2 3
+-+-+-+
|.....|
+.+.+.+
|.|.|.|
+-+-+-+

6

2 3
+-+-+-+
|...|.|
+.+.+.+
|.|...|
+-+-+-+

4

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

15

提示

在第一个样例中，如果你封闭房间 $(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)$ 之间建造一个新的门道。

上述改造后的配置如下所示。

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