Maze Game for the Movie Ticket

In this problem, two brilliant kids, AA and YY, decide who will get a movie ticket by playing a maze game. The game is played on an \(N \times M\) maze. Each cell is either accessible (denoted by .) or blocked (denoted by #). The game rules are as follows:

• First, AA chooses any accessible cell in the maze to place a single game piece. That cell is now considered visited.
• Then, the two players take turns moving the piece to an adjacent cell (up, down, left, right). Note: YY moves first after AA places the piece.
• No cell can be entered more than once and the piece cannot be moved into blocked cells.
• The game ends when the current player cannot make a move. The last player to make a valid move wins.

For example, consider the maze below (rows are given top to bottom):

.##
...
#.#

If AA places the piece at \((1,1)\) (using 1-indexed coordinates), then no matter how YY plays, AA cannot force a win. However, if AA places the piece at \((3,2)\) or \((2,3)\), there is a winning strategy for AA. In the case of placing at \((3,2)\), YY’s only move is to \((2,2)\) and then AA can move to \((2,3)\) to secure the win.

Assuming both players play optimally, determine whether AA can secure the ticket by choosing an appropriate starting cell.

Note: All formulas are written in \(\LaTeX\) (e.g. \(N \times M\), \((i,j)\)).

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of rows and columns of the maze. The following \(N\) lines each contain a string of length \(M\), composed of characters . (accessible cell) and # (blocked cell).

outputFormat

Output a single line containing Yes if AA can guarantee a win by choosing some starting cell, otherwise output No.

sample

3 3
.##
...
#.#

Yes