#2985. [NOIP1997 提高组] 棋盘上的素数

[NOIP1997 提高组] 棋盘上的素数

题目背景

NOIP1997 提高组第一题

题目描述

N×NN \times N1N101 \le N \le 10)的棋盘上,填入 1,2,,N21, 2, \dots, N ^ 2N2N ^ 2 个数,使得任意两个相邻的数之和为素数。

例如:当 N=2N = 2 时,有:

11 22
44 33

其相邻数的和为素数的有:

1+2,1+4,4+3,2+31+2,1+4,4+3,2+3

N=4N=4 时,一种可以填写的方案如下:

11 22 1111 1212
1616 1515 88 55
1313 44 99 1414
66 77 1010 33

在这里我们约定:左上角的格子里必须填数字 11

输入格式

一个数 NN

输出格式

如有多种解,则输出第一行、第一列之和为最小的排列方案;若无解,则输出 NO

样例

1
NO
2
1 2
4 3