Grid Path Conversion

You are given an n × m grid where each cell is either . (open) or # (blocked). Your task is to determine whether there exists a path from the top-left cell (cell (1,1)) to the bottom-right cell (cell (n,m)). You are allowed to convert at most one blocked cell into an open cell in order to enable a path.

Important: The starting cell and the destination cell cannot be converted; if either is blocked initially, the answer is NO.

A valid move is to a cell that is adjacent in one of the four cardinal directions (up, down, left, right). Formally, let the grid have indices from 1 to n in rows and 1 to m in columns. A move from cell (i,j) can be made to (i+1,j), (i-1,j), (i,j+1) or (i,j-1) provided the cell exists and is open.

If there exists a valid path, output YES; otherwise output NO.

The problem can be formulated mathematically as follows: Given a grid G of size \(n \times m\) where \(G_{ij} \in \{'.', '#'\}\), determine if there exists a sequence of coordinates \((i_1,j_1), (i_2,j_2), \ldots, (i_k,j_k)\) such that \( (i_1,j_1) = (1,1) \), \( (i_k,j_k) = (n,m) \), each move is adjacent (Manhattan distance 1), and after optionally converting at most one cell (except (1,1) and (n,m)) from # to ., all cells along the path are open.

inputFormat

The input is given via stdin in the following format:

 n m
 grid_row_1
 grid_row_2
 ...
 grid_row_n

Here, the first line contains two space-separated integers \(n\) and \(m\). Each of the next \(n\) lines contains a string of length \(m\) consisting only of the characters . and #, representing one row of the grid.

outputFormat

Output a single line to stdout: YES if it is possible to find a path from the top-left to the bottom-right cell (with at most one conversion allowed), otherwise output NO.

## sample

3 3
.#.
#.#
...

YES