ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

## I. Cutting a Square

Time limit: 1.0 second
Memory limit: 64 MB
After Vasya has finished his homework, he devotes himself to the following puzzle. He takes a white sheet of squared paper of size N × N cells, selects a non-empty connected subset of cells, and paints this subset black. When he has cut out the black piece, exactly one white piece is left. Then Vasya reunites the pieces into the original square and puts it onto an infinite table. Now his task is to disjoin the pieces by moving one of them along the table surface far from another in such a way that both pieces always stay in total contact with the table. For example, in the figure there are squares 5 × 5. In the first case the pieces can be separated and in the second case this is impossible.
Once Petr came to visit Vasya. He saw Vasya's occupation and wanted to help his best friend by writing a program that determines if the black and white pieces can be separated.

### Input

The first line contains the integer N (3 ≤ N ≤ 1000). In the next N lines containing N symbols each, the colors of the square's cells are given. Symbols 0 denote white and symbols 1 denote black. It is guaranteed that both pieces are connected with respect to cells' sides (for example, two cells with a common vertex but without common sides are not considered to be a connected piece).

### Output

Output “Yes” if the pieces can be separated, and “No” otherwise.

### Samples

inputoutput
```5
10001
10001
10001
11111
11111
```
```Yes
```
```5
11011
11011
10001
11111
11111
```
```No
```
Problem Author: Alexander Toropov
Problem Source: XIII-th USU Junior Contest, October 2006
To submit the solution for this problem go to the Problem set: 1497. Cutting a Square