Maze Path Validation

You are given an n x n maze where each cell is either a path or a wall. A cell with a value 0 represents a free path, and a cell with a value 1 represents a wall. The maze always has its starting point at the top-left corner (0, 0) and the destination at the bottom-right corner (n-1, n-1). It is guaranteed that the starting and ending cells are free (i.e. contain 0).

Your task is to determine whether there exists a valid path from the start to the destination. The movement is allowed only in four directions: up, down, left, and right. This problem can be solved using Depth-First Search (DFS) or Breadth-First Search (BFS).

Input and Output

The first line of input contains an integer n denoting the size of the maze. The next n lines each consist of n space-separated integers (0 or 1) representing the maze grid.

Output YES if there exists a valid path from the start to the destination, and NO otherwise.

Note: If you prefer, you can also implement a maze generator; however, for this problem the maze is provided as input.

inputFormat

The input will be read from standard input and is formatted as follows:

• The first line contains an integer n indicating the number of rows and columns in the maze.
• The following n lines each contain n space-separated integers where each integer is either 0 (free path) or 1 (wall).

outputFormat

Print a single line to standard output: YES if there exists a valid path from the start cell (0,0) to the destination cell (n-1,n-1); otherwise, print NO.

## sample

3
0 1 1
0 0 1
1 0 0

YES

</p>