Problem11372--环(Ring)

11372: 环(Ring)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

一个 $n×n\ (n\leq 6)$ 的矩阵,可以分成一些环。如图中,$n=5$,可以划分成 $3$ 个环。
每个环上的数字都可以沿着环顺时针或者逆时针转动,每次转动只能将任意一个环顺时针或者逆时针转动一格。
初始状态如图a,将矩阵从左到右、从上到下依次用 $1$ 到 $n×n$ 填满。
现在给你一个局面,请问至少通过多少次环的转动能使矩阵恢复到初始状态?

例如,图b的局面可以通过,最外圈逆时针转动两格,第二圈顺时针转动一格,恢复到初始状态(图a),即至少转动三次。

Input

第一行输入一个正整数 $n$。

接下来 $n$ 行,每行输入 $n$ 个用空格隔开的正整数,第 $i$ 行第 $j$ 个数 $a_{ij}\ (a_{ij}≤1000)$,表示给定的 $n×n$ 的矩阵局面。

Output

若给定的矩阵局面可以通过环的转动回到初始状态,则输出两行,第一行为 YES,第二行为一个非负整数,表示至少需要转动几次;否则,输出 NO

Sample 1 Input

5
11 6 1 2 3
16 8 9 14 4
21 7 13 19 5
22 12 17 18 10
23 24 25 20 15

Sample 1 Output

YES
3

Sample 2 Input

4
1 2 3 4
5 6 7 8
9 9 11 12
13 14 15 16

Sample 2 Output

NO

Source/Category