Valid Path in Grid

You are given a square grid of size \( n \times n \). Each cell in the grid is either walkable (denoted by 0) or blocked (denoted by 1). Your task is to determine whether there exists a valid path from the top-left cell (at position \( (0,0) \)) to the bottom-right cell (at position \( (n-1,n-1) \)).

You are only allowed to move either to the right or down at any step. The path is valid only if all visited cells are walkable.

Input Format:

• The first line contains a single integer \( n \) — the size of the grid.
• The next \( n \) lines each contain \( n \) integers (either 0 or 1) separated by spaces representing the grid.

Output Format:

• Print YES if there exists a valid path from the top-left to the bottom-right cell, otherwise print NO.

The problem can be mathematically stated as follows:

[ \text{Find if } \exists ; { (x_i, y_i) }_{i=0}^{k} \text{ such that } (x_0, y_0) = (0, 0), ; (x_k, y_k) = (n-1, n-1), ; \forall i,; grid[x_i][y_i]=0, ]

[ \text{and } (x_{i+1}, y_{i+1}) - (x_i, y_i) \in { (1, 0), (0, 1) } \text{ for } 0 \le i < k. ]

inputFormat

The input is given via standard input. The first line contains an integer \( n \) denoting the size of the grid. The next \( n \) lines consist of \( n \) integers each separated by space, where each integer is either 0 (walkable) or 1 (blocked).

outputFormat

Output a single line to standard output: YES if a valid path exists, or NO if it does not.

## sample

3
0 1 0
0 0 1
1 0 0

YES