Find the Snake Path in a Grid

Given an \(n \times m\) grid of lowercase English letters, your task is to determine if there exists a valid continuous path that spells out the word snake. The path must start with the letter s (at index 0 of the word) and end with the letter e (at index 4). You can move in four directions: up, down, left, and right. Note that each cell of the grid can be used at most once in the path.

Constraints: \(1 \le n, m \le 1000\).

If a valid path is found, output YES; otherwise, output NO.

inputFormat

The first line of input contains two integers n and m, representing the number of rows and columns in the grid, respectively. Each of the following n lines contains a string of length m, representing a row of the grid.

For example:

5 5
saske
najnk
akepq
kspoi
ereek

outputFormat

Output a single line containing either YES if there exists a path that spells snake, or NO otherwise.

5 5
saske
najnk
akepq
kspoi
ereek

YES