Maze Escape

Farmer John built a huge maze in his field, entirely enclosed by fences, with exactly two openings on its boundary that serve as exits. Even more remarkably, the maze is a perfect maze – that is, from any cell inside the maze there is one unique simple path to an exit.

You are given the maze width \(W\) (\(1 \leq W \leq 38\)) and height \(H\) (\(1 \leq H \leq 100\)). The maze is represented in a drawing of \(2H+1\) lines, each line having \(2W+1\) characters, according to a fixed format. In the maze drawing, the fence posts appear only at positions with odd row and column indices.

Your task is to compute the number of steps required from the worst-case starting cell – that is, find the cell for which even an optimal escape route requires the most steps to exit the maze. Note that moves are allowed only horizontally or vertically (along the X or Y axis) and each move to an adjacent cell (including the final step leaving the maze) counts as one step.

inputFormat

The first line contains two integers, \(W\) and \(H\), representing the width and height of the maze. Following this, there are \(2H+1\) lines, each containing \(2W+1\) characters that together form the maze drawing.

outputFormat

Output a single integer: the maximum number of steps required (over all cells) to reach an exit when following an optimal route.

sample

5 3
+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     |  
+-+ +-+-+-+

9