Path Existence in a Grid

You are given a grid of size n x m consisting of characters '.' and '#'. The character '.' represents a cell that can be traversed, while '#' represents an obstacle.

Your task is to determine whether there exists a path from the top-left cell (cell at row 1, column 1) to the bottom-right cell (cell at row n, column m). Movement is allowed only in the four cardinal directions: up, down, left, and right. Diagonal moves are not allowed.

Note: If the starting cell or the target cell is blocked (i.e. contains '#'), no valid path exists.

Formally, you need to decide if there exists a sequence of moves such that if we denote the current cell by \((i, j)\), you can move to \((i+1, j)\), \((i-1, j)\), \((i, j+1)\) or \((i, j-1)\) provided the new cell is inside the grid and not blocked.

inputFormat

The first line of input contains two integers n and m (1 ≤ n, m ≤ 1000), which represent the number of rows and columns of the grid respectively.

Each of the following n lines contains a string of m characters (each either '.' or '#'), representing the grid.

outputFormat

Output a single line containing the string "YES" if there is a path from the top-left cell to the bottom-right cell, otherwise output "NO".

3 3
...
.#.
...

YES