AndyMan68 has recently gotten bored of word searches, and decided to search for numbers instead! He is given an ~N~ by ~N~ grid, with each cell being a random integer from ~1~ to ~N~ inclusive. To solve the number search, he must find a path of numbers that goes from ~1, 2, ... N~. More specifically, a path is valid if a cell with number ~a_i~ is adjacent to a cell with ~a_i + 1~ for all ~a_i~ from ~1~ to ~N~ along the path.

Help AndyMan68 determine if there exists a solution to the number search!

Input Specification

The first line contains the integer ~N~ ~(1 \le N \le 10)~.

The next ~N~ lines contains ~N~ spaced integers, where each integer is from ~1~ to ~N~ inclusive.

Output Specification

Output YES if there exists a solution to the number search, otherwise output NO.

Sample Input 1

4
3 2 1 4
2 3 1 1
1 3 2 2
3 4 1 4

Output for Sample Input 1

YES

Sample Input 2

3
2 1 3
1 2 2
3 1 3

Output for Sample Input 2

NO