Simple Puzzle

Alpc83 is proud of his IQ, so he usually try to challenge the puzzle which is famous but more difficult than what we have known. Some days ago, he played the eight digits puzzle, and he thought it’s so easy. Then he want to challenge a N*N-1 digits puzzle whose rules are same with the eight digits puzzle. Firstly he have all the numbers from 0 to N*N-1 arranged in N rows and N columns randomly. Because he don’t want to waste time, he hope to make sure whether he can finally solve the puzzle if he is clever enough. Now he ask you for help.
(Ps. Don’t you know the eight digits puzzle? Oh, my god! Let me tell you: you have all numbers from 0 to 8 arranged in 3 rows and 3 columns. You are allowed to switch two adjacent elements (horizontally or vertically), only if one of them has the value 0. You have to decide whether there exists a sequence of moves which brings the puzzle in the initial state into the final state.)
In this puzzle , we will give you a initial state, and we set the final state is:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
(n=4 for example)

Each case starts with a line contains the integer N.
The following N lines describe the initial state, each of them containing n integers, describing the initial state of the puzzle.
A line with N = 0 indicates the end of the input; do not write any output for this case. (N<=300)

For each test case, print "YES" if the final state can be reached after several moves or "NO", if such a thing is impossible.

2
2 1 
3 0
0

NO

alpc83

2010 ACM-ICPC Multi-University Training Contest（16）——Host by NUDT