Hamiltonian Path in a Grid

You are given an N x M grid consisting of . (free cell) and # (blocked cell). Your task is to determine whether there exists a simple path from the top‐left cell to the bottom‐right cell that visits every free cell exactly once.

A simple path is one that does not visit any cell more than once. The path can move in the four cardinal directions: up, down, left, and right.

Note: If either the starting cell (top‐left) or the destination cell (bottom‐right) is blocked, the answer is NO.

The problem can be formally stated as follows:

Given an integer N and M and a grid of N rows and M columns, let F be the number of free cells (cells containing .). Determine if there exists a path starting at cell (1,1) and ending at cell (N,M) that visits exactly F cells (each free cell exactly once).

The answer should be YES if such a path exists, and NO otherwise.

inputFormat

The first line contains two integers N and M representing the number of rows and columns of the grid.

This is followed by N lines, each containing a string of length M consisting only of the characters . and #, which represent free and blocked cells respectively.

Input is given via standard input.

outputFormat

Output a single line containing YES if there exists a simple path from the top‐left cell to the bottom‐right cell that visits every free cell exactly once; otherwise, output NO.

Output the answer to standard output.

## sample

3 3
..#
.#.
..#

NO