Matrix Pathfinding

You are given an n × n binary matrix, where each cell contains either a 0 or a 1. Your task is to determine if there exists a valid path from the top-left cell to the bottom-right cell. You can only move either to the right or down, and you may only traverse cells that contain the value 1.

Path Constraints:

• You may only move right (i.e. from cell (i, j) to (i, j+1)) or down (i.e. from cell (i, j) to (i+1, j)).
• The starting cell (top-left) and the destination cell (bottom-right) must both contain a 1.

Determine if such a path exists. If it does, output YES; otherwise, output NO.

The answer should be output in a single line.

inputFormat

The input is given via standard input (stdin) with the following format:

1. The first line contains an integer n, the size of the matrix.
2. The next n lines each contain n space-separated integers (each either 0 or 1), which represent the rows of the matrix.

Note: It is guaranteed that 1 ≤ n ≤ 1000.

outputFormat

Output a single line to standard output (stdout) that is either YES if there exists a valid path from the top-left to the bottom-right, or NO if there is no such path.

## sample

3
1 0 0
1 1 0
0 1 1

YES